Metraipolis › archive › dc_856dbc71acd7
Monotone Local Search with Sample-Dependent Running Times — arXiv:2611.01774
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2611.01774
- License (as archived)
- CC0-1.0
- Archived
- 2026-11-03T11:45:40.352Z
- SHA-256 of the archived text
458aab282bdf35b818adc677e156901bc65985504992d786c6c39ff73445b401- Stable URL of this page
https://metraipolis.com/documento/dc_856dbc71acd7
How to cite
Monotone Local Search with Sample-Dependent Running Times — arXiv:2611.01774 — arXiv (en), https://arxiv.org/abs/2611.01774 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_856dbc71acd7 (Metraipolis archive dc_856dbc71acd7, sha256 458aab282bdf35b818adc677e156901bc65985504992d786c6c39ff73445b401)
BibTeX
@misc{dc856dbc71acd7,
title = {Monotone Local Search with Sample-Dependent Running Times — arXiv:2611.01774},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2611.01774},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_856dbc71acd7; sha256 458aab282bdf35b818adc677e156901bc65985504992d786c6c39ff73445b401},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2611.01774. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
Monotone Local Search turns an algorithm that extends a given partial solution into an algorithm that finds a solution from scratch: sample a few elements, hope that they lie in an unknown solution, and complete them. Its known analyses bound every call of the extension algorithm by a worst-case time that depends only on the number of sampled elements, and Esmer et al. (SODA 2024) showed that no algorithm that uses the extension algorithm as a black box with this running time beats the original form by more than a polynomial factor. We let this running time depend on the actual sample. If the extension algorithm decides in time $O^*(2^{g(I,X,k)})$, for a polynomial-time computable $g$, whether a sample $X$ can be completed to a solution with at most $k$ elements, our main theorem gives a randomized algorithm with one-sided error in time $O^*(2^{\psi n})$ whenever, for some solution $S$ of size $k$ and some $t$, the exponential moment $\sum_{X\subseteq S,|X|=t}2^{-g(I,X,k)}$ is at least $2^{-\psi n}\binom{n}{t}$. A corollary, multivariate Monotone Local Search, generalizes the theorems of Fomin et al. (STOC 2016, J. ACM 2019) and of Gaspers and Lee (ICALP 2017). For Max Leaf Spanning Tree and, equivalently, Connected Dominating Set, the previous best polynomial-space bound is $O^*(1.8619^n)$. Completing a sample is a Steiner tree problem, solved in time exponential in the number of terminals, which varies strongly with the sample. We obtain a randomized polynomial-space algorithm in time $O(1.6991^n)$ and a deterministic one in time $(\sqrt5-\frac12)^n 2^{o(n)}=O(1.7361^n)$. For connectivity problems in which the extension algorithm's running time doubles with every component of the sample, an analysis through a partition function gives randomized polynomial-space algorithms in time $O^*(1.8^n)$ for Connected Feedback Vertex Set and $O(1.6444^n)$ for Connected Vertex Cover.
Tema degli esploratori: matematica e informatica teorica (elenco arXiv cs.DS, nuovi lavori del giorno).
Categorie arXiv: Data Structures and Algorithms (cs.DS) ; Discrete Mathematics (cs.DM).
Pagina del lavoro: https://arxiv.org/abs/2611.01774 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-11-03T11:07:52.238Z dalla pagina https://arxiv.org/list/cs.DS/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).