Metraipolis › archive › dc_280fc16f3c69
Paying for Fractional Error: Tight Constant-Round Approximation of Covering Problems with Short Broadcasts — arXiv:2611.02057
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2611.02057
- License (as archived)
- CC0-1.0
- Archived
- 2026-11-03T18:26:51.319Z
- SHA-256 of the archived text
3c468145d10f1b4ae937f53fce70151e85281c7dbd68d1f23c5214f3de292c1f- Stable URL of this page
https://metraipolis.com/documento/dc_280fc16f3c69
How to cite
Paying for Fractional Error: Tight Constant-Round Approximation of Covering Problems with Short Broadcasts — arXiv:2611.02057 — arXiv (en), https://arxiv.org/abs/2611.02057 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_280fc16f3c69 (Metraipolis archive dc_280fc16f3c69, sha256 3c468145d10f1b4ae937f53fce70151e85281c7dbd68d1f23c5214f3de292c1f)
BibTeX
@misc{dc280fc16f3c69,
title = {Paying for Fractional Error: Tight Constant-Round Approximation of Covering Problems with Short Broadcasts — arXiv:2611.02057},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2611.02057},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_280fc16f3c69; sha256 3c468145d10f1b4ae937f53fce70151e85281c7dbd68d1f23c5214f3de292c1f},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2611.02057. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
We present a general framework for deterministic constant-round approximation of covering problems in sparse networks in the broadcast CONGEST model, where every vertex broadcasts the same $O(\log n)$-bit message to all its neighbors. The framework combines two independent tools. The first is a solver that computes a $(1+\delta)$-approximate solution of any local covering linear program with bounded positive integer costs on every class that excludes a fixed minor. The second is a rounding principle: a rounding rule that saves a fixed fraction of its own output, for every feasible input, pays for a solver error fixed in advance, so that an approximate fractional solution yields an exact coefficient. For ordinary domination, we achieve a $2a+1$ approximation against the fractional optimum $\gamma_f(G)$ for every fixed rational $a\ge1$, whenever every minor has a ratio of edges to vertices of at most $a$. On planar graphs this is seven, matching the lower bound of Hilke, Lenzen, and Suomela. The coefficients are also optimal at bounded treewidth and pathwidth, for $K_t$-minor-free graphs with $3\le t\le9$, on triangle-free planar graphs (five), and on planar graphs of large girth, where it approaches the optimal three. On every fixed surface the exact bound is $7\gamma(G)$, and we show that a bound of $7\gamma_f(G)$ is impossible on some fixed surfaces even sequentially. For total domination, on graphs without isolated vertices and under the same minor-density assumption, the exact coefficient is $2a$ against the fractional optimum, including the optimal six on planar graphs. Red-blue domination, and hence set cover and hitting set on planar incidence graphs, has the optimal limiting coefficient four. Our method also gives randomized constant-round and deterministic $O(\log^* n)$-round $(1+\varepsilon)$-approximation schemes, with the randomized cost guarantee holding in expectation. Tema degli esploratori: calcolo e infrastrutture (elenco arXiv cs.DC, nuovi lavori del giorno). Categorie arXiv: Data Structures and Algorithms (cs.DS) ; Distributed, Parallel, and Cluster Computing (cs.DC). Pagina del lavoro: https://arxiv.org/abs/2611.02057 — 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-03T18:10:22.859Z dalla pagina https://arxiv.org/list/cs.DC/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).