Simple Length-Constrained Minimum Spanning Trees
Fuente:
arXiv
Salvato in:
| Autori principali: | , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866916794615201792 |
|---|---|
| author | Hershkowitz, D Ellis Huang, Richard Z |
| author_facet | Hershkowitz, D Ellis Huang, Richard Z |
| contents | In the length-constrained minimum spanning tree (MST) problem, we are given an $n$-node edge-weighted graph $G$ and a length constraint $h \geq 1$. Our goal is to find a spanning tree of $G$ whose diameter is at most $h$ with minimum weight. Prior work of Marathe et al.\ gave a poly-time algorithm which repeatedly computes maximum cardinality matchings of minimum weight to output a spanning tree whose weight is $O(\log n)$-approximate with diameter $O(\log n)\cdot h$.
In this work, we show that a simple random sampling approach recovers the results of Marathe et al. -- no computation of min-weight max-matchings needed! Furthermore, the simplicity of our approach allows us to tradeoff between the approximation factor and the loss in diameter: we show that for any $ε\geq 1/\operatorname{poly}(n)$, one can output a spanning tree whose weight is $O(n^ε/ ε)$-approximate with diameter $O(1/ε)\cdot h$ with high probability in poly-time. This immediately gives the first poly-time $\operatorname{poly}(\log n)$-approximation for length-constrained MST whose loss in diameter is $o(\log n)$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2410_08170 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Simple Length-Constrained Minimum Spanning Trees Hershkowitz, D Ellis Huang, Richard Z Data Structures and Algorithms In the length-constrained minimum spanning tree (MST) problem, we are given an $n$-node edge-weighted graph $G$ and a length constraint $h \geq 1$. Our goal is to find a spanning tree of $G$ whose diameter is at most $h$ with minimum weight. Prior work of Marathe et al.\ gave a poly-time algorithm which repeatedly computes maximum cardinality matchings of minimum weight to output a spanning tree whose weight is $O(\log n)$-approximate with diameter $O(\log n)\cdot h$. In this work, we show that a simple random sampling approach recovers the results of Marathe et al. -- no computation of min-weight max-matchings needed! Furthermore, the simplicity of our approach allows us to tradeoff between the approximation factor and the loss in diameter: we show that for any $ε\geq 1/\operatorname{poly}(n)$, one can output a spanning tree whose weight is $O(n^ε/ ε)$-approximate with diameter $O(1/ε)\cdot h$ with high probability in poly-time. This immediately gives the first poly-time $\operatorname{poly}(\log n)$-approximation for length-constrained MST whose loss in diameter is $o(\log n)$. |
| title | Simple Length-Constrained Minimum Spanning Trees |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2410.08170 |