Marthe Bonamy, Nicolas Bousquet, Marc Heinrich, Takehiro Ito, Yusuke Kobayashi, Arnaud Mary, Moritz Mühlenthaler, Kunihiro Wasa
2019-04-12
We study the perfect matching reconfiguration problem: Given two perfect matchings of a graph, is there a sequence of flip operations that transforms one into the other? Here, a flip operation exchanges the edges in an alternating cycle of length four. We are interested in the complexity of this decision problem from the viewpoint of graph classes. We first prove that the problem is PSPACE-complete even for split graphs and for bipartite graphs of bounded bandwidth with maximum degree five. We then investigate polynomial-time solvable cases. Specifically, we prove that the problem is solvable in polynomial time for strongly orderable graphs (that include interval graphs and strongly chordal graphs), for outerplanar graphs, and for cographs (also known as
-free graphs). Furthermore, for each yes-instance from these graph classes, we show that a linear number of flip operations is sufficient and we can exhibit a corresponding sequence of flip operations in polynomial time.
Hanna Geppert, Martin Wilhelm
2019-04-03
Number types for exact computation are usually based on directed acyclic graphs. A poor graph structure can impair the efficency of their evaluation. In such cases the performance of a number type can be drastically improved by restructuring the graph or by internally balancing error bounds with respect to the graph's structure. We compare advantages and disadvantages of these two concepts both theoretically and experimentally.
Chris Schwiegelshohn, Uwe Schwiegelshohn
2019-04-12
We investigate online scheduling with commitment for parallel identical machines. Our objective is to maximize the total processing time of accepted jobs. As soon as a job has been submitted, the commitment constraint forces us to decide immediately whether we accept or reject the job. Upon acceptance of a job, we must complete it before its deadline
that satisfies , with and being the processing time and the submission time of the job, respectively while is the slack of the system. Since the hard case typically arises for near-tight deadlines, we consider . We use competitive analysis to evaluate our algorithms. Our first main contribution is a deterministic preemptive online algorithm with an almost tight competitive ratio on any number of machines. For a single machine, the competitive factor matches the optimal bound of the greedy acceptance policy. Then the competitive ratio improves with an increasing number of machines and approaches as the number of machines converges to infinity. This is an exponential improvement over the greedy acceptance policy for small . In the non-preemptive case, we present a deterministic algorithm on machines with a competitive ratio of . This matches the optimal bound of of the greedy acceptance policy for a single machine while it again guarantees an exponential improvement over the greedy acceptance policy for small and large . In addition, we determine an almost tight lower bound that approaches for large and small .
Fedor V. Fomin, Petr A. Golovach, Fahad Panolan, Kirill Simonov
2019-04-12
We consider
-Rank- Approximation over GF(2), where for a binary matrix and a positive integer , one seeks a binary matrix of rank at most , minimizing the column-sum norm . We show that for every , there is a randomized -approximation algorithm for -Rank- Approximation over GF(2) of running time . This is the first polynomial time approximation scheme (PTAS) for this problem.
Peng-Cheng Lin, Wan-Lei Zhao
2019-04-03
Hierarchical navigable small world (HNSW) graphs get more and more popular on large-scale nearest neighbor search tasks since the source codes were released two years ago. The attractiveness of this approach lies in its superior performance over most of the known nearest neighbor search approaches as well as its genericness to various distance measures. In this paper, several comparative studies have been conducted on this search approach. The role of hierarchical structure in HNSW and the function of HNSW graph itself are investigated. We find that the hierarchical structure in HNSW could not achieve "a much better logarithmic complexity scaling" as it was claimed in the paper, particularly on high dimensional data. Moreover, we find that similar high search speed efficiency as HNSW could be achieved with the support of flat k-NN graph after graph diversification. Finally, we point out the difficulty, that is faced by most of the graph based search approaches, is directly linked to "curse of dimensionality". HNSW, like other graph based approaches, is unable to address such difficulty.
Jorge Garza Vargas, Archit Kulkarni
2019-04-12
We study the Lanczos algorithm where the initial vector is sampled uniformly from
. Let be an Hermitian matrix. We show that when run for few iterations, the output of the algorithm on is almost deterministic. For instance, we show that there exists depending only on a certain global property of the spectrum of (in particular, not depending on ) such that when Lanczos is run for at most iterations, the Jacobi coefficients and the Ritz values deviate from their medians by with probability at most , for . Furthermore, we show that the Lanczos algorithm fails with high probability to identify outliers of the spectrum when run for at most iterations, where again depends only on the same global property of the spectrum of . Classical results imply that the bound is tight up to a constant factor. Our techniques also yield asymptotic results: Suppose we have a sequence of Hermitian matrices whose spectral distributions converge in Kolmogorov distance with rate to a density, for some . Then we show that for large enough , and for , the Ritz values after iterations concentrate around the roots of the th orthogonal polynomial with respect to the limiting density.
Kai DeLorenzo, Shelby Kimmel, R. Teal Witter
2019-04-12
We present quantum algorithms for various problems related to graph connectivity. We give simple and query-optimal algorithms for cycle detection and odd-length cycle detection (bipartiteness) using a reduction to st-connectivity. Furthermore, we show that our algorithm for cycle detection has improved performance under the promise of large circuit rank or a small number of edges. We also provide algorithms for detecting even-length cycles and for estimating the circuit rank of a graph. All of our algorithms have logarithmic space complexity.
Yuri Faenza, Telikepalli Kavitha
2019-04-11
Let
be an instance of the stable marriage problem where every vertex ranks its neighbors in a strict order of preference. A matching in is popular if does not lose a head-to-head election against any matching . That is, where (similarly, ) is the number of votes for (resp., ) in the -vs- election. Popular matchings are a well-studied generalization of stable matchings, introduced with the goal of enlarging the set of admissible solutions, while maintaining a certain level of fairness. Stable matchings are, in fact, popular matchings of minimum size. Unfortunately, unlike in the case of stable matchings, it is NP-hard to find a popular matching of minimum cost, when a linear cost function is given on the edge set -- even worse, the min-cost popular matching problem is hard to approximate up to any factor. The goal of this paper is to obtain efficient algorithms for computing desirable matchings (wrt cost) by paying the price of mildly relaxing popularity. Call a matching quasi-popular if for every matching . Our main positive result is a bi-criteria algorithm that finds in polynomial time a quasi-popular matching of cost at most opt, where opt is the cost of a min-cost popular matching. Key to the algorithm are a number of results for certain polytopes related to matchings and that we believe to be of independent interest. In particular, we give a polynomial-size extended formulation for an integral polytope sandwiched between the popular and quasi-popular matching polytopes. We complement these results by showing that it is NP-hard to find a quasi-popular matching of minimum cost, and that both the popular and quasi-popular matching polytopes have near-exponential extension complexity.
He Sun, Luca Zanetti
2016-07-18
Graph clustering is a fundamental computational problem with a number of applications in algorithm design, machine learning, data mining, and analysis of social networks. Over the past decades, researchers have proposed a number of algorithmic design methods for graph clustering. However, most of these methods are based on complicated spectral techniques or convex optimisation, and cannot be applied directly for clustering many networks that occur in practice, whose information is often collected on different sites. Designing a simple and distributed clustering algorithm is of great interest, and has wide applications for processing big datasets. In this paper we present a simple and distributed algorithm for graph clustering: for a wide class of graphs that are characterised by a strong cluster-structure, our algorithm finishes in a poly-logarithmic number of rounds, and recovers a partition of the graph close to an optimal partition. The main component of our algorithm is an application of the random matching model of load balancing, which is a fundamental protocol in distributed computing and has been extensively studied in the past 20 years. Hence, our result highlights an intrinsic and interesting connection between graph clustering and load balancing. At a technical level, we present a purely algebraic result characterising the early behaviours of load balancing processes for graphs exhibiting a cluster-structure. We believe that this result can be further applied to analyse other gossip processes, such as rumour spreading and averaging processes.
Benjamin Doerr, Timo Kötzing
2019-04-11
Drift analysis aims at translating the expected progress of an evolutionary algorithm (or more generally, a random process) into a probabilistic guarantee on its run time (hitting time). So far, drift arguments have been successfully employed in the rigorous analysis of evolutionary algorithms, however, only for the situation that the progress is constant or becomes weaker when approaching the target. Motivated by questions like how fast fit individuals take over a population, we analyze random processes exhibiting a multiplicative growth in expectation. We prove a drift theorem translating this expected progress into a hitting time. This drift theorem gives a simple and insightful proof of the level-based theorem first proposed by Lehre (2011). Our version of this theorem has, for the first time, the best-possible linear dependence on the growth parameter
(the previous-best was quadratic). This gives immediately stronger run time guarantees for a number of applications.
