In May 2018, Ryan McIntyre defended his masters thesis (at CSUCI under my supervision) on Bounding the size of minimal clique covers. We followed up with a publication of the results in the Journal of Discrete Algorithms (https://doi.org/10.1016/j.jda.2018.03.002) [post], and now, two years later, our results are cited and built upon in an interesting paper Static beam placement and frequency plan algorithms for LEO constellations (https://doi.org/10.1002/sat.1345) written by an Astronautics research group at MIT.
What is interesting about this is the serendipitous manner in which results build on each other: our result consisted in a partial solution to an original problem in combinatorics posed by the itinerant mathematician Paul Ërdos (posed in the mid 1960s), which we then used to partially solve a problem related to string indeterminates (also in this case working on previous results of Joel Helling [post]), which are related to genetics. Now, our work is being used to solve the problem of satellite allocation.
My book, An Introduction to the Analysis of Algorithms, has been identified by the publisher, World Scientific, as one of the most downloaded ebooks. See my page http://www.msoltys.com/book with all the book details and resources (slides, GitHub repository with implementations of all algorithms, solutions to problems, errata, etc.).
In this paper, A new formal framework for Stringology is proposed, which consists of a three-sorted logical theory designed to capture the combinatorial reasoning about finite strings. We propose a language for expressing assertions about strings, and study in detail two sets of formulas , a set of formulas decidable in polytime, and , a set of formulas with the property that those provable in yield polytime algorithms.
Happy to announce that Ryan McIntyre’s masters thesis results, An improved upper bound and algorithm for clique covers (prelim), will be published as our joint paper in Journal of Discrete Algorithms.
An interesting feature of indeterminate strings is the natural correspondence with undirected graphs. One aspect of this correspondence is the fact that the minimal alphabet size of indeterminates representing any given undirected graph corresponds to the size of the minimal clique cover of this graph. This paper first considers a related problem proposed in Helling 2017: characterize $latex\Theta_n(m)$, which is the size of the largest possible minimal clique cover (i.e., an exact upper bound), and hence alphabet size of the corresponding indeterminate, of any graph on vertices and edges. We provide improvements to the known upper bound for . Helling 2017 also presents an algorithm which finds clique covers in polynomial time. We build on this result with an original heuristic for vertex sorting which significantly improves their algorithm’s results, particularly in dense graphs.
This work was the result of building on Helling 2017 (see this post) and of a year of research undertaken by Ryan McIntyre under my (Michael Soltys) supervision at the California State University Channel Islands.
We present a matrix permutation algorithm for computing a minimal vertex cover from a maximal matching in a bipartite graph. Our algorithm is linear time and linear space, and provides an interesting perspective on a well known problem. Unlike most algorithms, it does not use the concept of alternating paths, and it is formulated entirely in terms of combinatorial operations on a binary matrix. The algorithm relies on permutations of rows and columns of a 0-1 matrix which encodes a bipartite graph together with its maximal matching. This problem has many important applications such as network switches which essentially compute maximal matchings between their incoming and outgoing ports.
Abstract: In this study, we provide mathematical and practice-driven justification for using [0, 1] normalization of inconsistency indicators in pairwise comparisons. The need for normalization, as well as problems with the lack of normalization, are presented. A new type of paradox of infinity is described.
Accepted for publication in the International Journal of Approximate Reasoning, April 2017.
A new paper: On normalization of inconsistency indicators in pairwise comparisons, by W.W. Koczkodaj, J.-P. Magnot, J. Mazurek, J.F. Peters, H. Rakhshani, M. Soltys, D. Strzałka, J. Szybowski and A. Tozzi.
Abstract: In this study, we provide mathematical and practice-driven justification for using [0,1] normalization of inconsistency indicators in pairwise comparisons. The need for normalization, as well as problems with the lack of normalization, are presented. A new type of paradox of infinity is described.
The paper can be found here: https://arxiv.org/abs/1702.07205v2
We (Neerja Mhaskar and Michael Soltys) had our paper presented at the Prague Stringology Conference; the paper introduces a new formal framework for Stringology, which consists of a three-sorted logical theory S designed to capture the combinatorial reasoning about finite words:
And these are the slides:
In a new paper, Square-free strings over alphabet lists, my PhD student Neerja Mhaskar and I, solve an open problem that was posed in A new approach to non repetitive sequences, by Jaroslaw Grytczuk, Jakub Kozik, and Pitor Micek, in arXiv:1103.3809, December 2010.
The problem can be stated as follows: Given an alphabet list $L=L_1,\ldots,L_n$, where $|L_i|=3$ and $0 \leq i \leq n$, can we always find a square-free string, $W=W_1W_2 \ldots W_n$, where $W_i\in L_i$? We show that this is indeed the case. We do so using an “offending suffix” characterization of forced repetitions, and a counting, non-constructive, technique. We discuss future directions related to finding a constructive solution, namely a polytime algorithm for generating square-free words over such lists.
Our paper will be presented and published in the 26th International Workshop on Combinatorial Algorithms (IWOCA), Verona, Italy, October 2015.