Name
Abstract | ||
|---|---|---|
We present a new perspective on the analysis of stochastic local search algorithms via linear algebra. Our key insight is that LLL-inspired convergence arguments can be seen as a method for bounding the spectral radius of a matrix specifying the algorithm to be analyzed. Armed with this viewpoint we give a unified analysis of all emph{entropy compression} applications, connecting backtracking algorithms to the LLL in the same fashion that existing analyses connect resampling algorithms to the LLL. We then give a new convergence condition that seamlessly handles resampling algorithms that can detect, and back away from, unfavorable parts of the state space. We give several applications of this condition, notably a new vertex coloring algorithm for arbitrary graphs that uses a number of colors that matches the algorithmic barrier for random graphs. Finally, we introduce a generalization of Kolmogorovu0027s notion of emph{commutative} algorithms, cast as matrix commutativity, which affords much simpler proofs both of the original results and of recent extensions. |
Year | Venue | Field |
|---|---|---|
2018 | arXiv: Discrete Mathematics | Discrete mathematics,Linear algebra,Random graph,Commutative property,Entropy compression,Local search (optimization),Lovász local lemma,Backtracking,State space,Mathematics |
DocType | Volume | Citations |
Journal | abs/1805.02026 | 0 |
PageRank | References | Authors |
0.34 | 19 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Dimitris Achlioptas | 1 | 2037 | 174.89 |
| Fotis Iliopoulos | 2 | 13 | 5.28 |
| Alistair Sinclair | 3 | 1506 | 308.40 |