Monotone Local Search with Sample-Dependent Running Times
Companion site
The trailer (3:23, with voice-over; captions in the player menu) walks through the paper’s results. Download the MP4 (1920×1080, 57 MB).
The paper in brief
Monotone Local Search turns an algorithm that extends a given partial solution into an exact algorithm that finds a solution from scratch: sample a few elements, hope that they lie in an unknown solution, and complete them. In all its known forms, the analysis bounds every call of the extension algorithm by a worst-case time that depends only on the number of sampled elements. The paper lets this bound depend on the sample itself, and its main theorem needs only that the exponential moments of the running-time exponent over the subsets of one solution are large.
For Max Leaf Spanning Tree, equivalently Connected Dominating Set, the fastest published polynomial-space algorithm runs in time \(O^{*}(1.8619^n)\). The paper’s bounds, all in polynomial space:
| Algorithm | Time | Type | In the paper |
|---|---|---|---|
| RS | \(O(1.7449^n)\) | randomized, one-sided error | Theorem 6.4 |
| Deterministic | \(O(1.7361^n)\) | deterministic | Theorem 10.4 |
| RS-θ | \(O(1.7204^n)\) | randomized, one-sided error | Theorem 7.2 |
| RSC | \(O(1.6991^n)\) | randomized, one-sided error | Theorem 8.1 |
The same theorem gives Connected Feedback Vertex Set in time \(O^{*}(1.8^n)\), Graph Motif and Connected Vertex Cover in time \(O(1.6444^n)\), and further applications listed in Table 2.
Where to go next
- Read the paper: the full text, section by section, with the same numbering as the PDF.
- Download the PDF of the same version.
- Download the short version (PDF, 28 pages): the main theorem and its corollaries with full proofs, and the applications in summary. Its numbering differs from the full version, which is the reference for every proof.