Metraipolis › archive › dc_7f430160a7db

Stochastic Gradient Meets Randomized Rounding: New Algorithms for Node-Weighted Steiner Problems — arXiv:2608.06807

Source
arXiv (en)
Original
https://arxiv.org/abs/2608.06807
License (as archived)
CC0-1.0
Archived
2026-10-23T15:11:00.770Z
SHA-256 of the archived text
a22e771199382c8ea2fcc739a0d0c140abe0607c35684bec5b761c4e64a31118
Stable URL of this page
https://metraipolis.com/documento/dc_7f430160a7db

How to cite

Stochastic Gradient Meets Randomized Rounding: New Algorithms for Node-Weighted Steiner Problems — arXiv:2608.06807 — arXiv (en), https://arxiv.org/abs/2608.06807 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_7f430160a7db (Metraipolis archive dc_7f430160a7db, sha256 a22e771199382c8ea2fcc739a0d0c140abe0607c35684bec5b761c4e64a31118)
BibTeX
@misc{dc7f430160a7db,
  title = {Stochastic Gradient Meets Randomized Rounding: New Algorithms for Node-Weighted Steiner Problems — arXiv:2608.06807},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2608.06807},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_7f430160a7db; sha256 a22e771199382c8ea2fcc739a0d0c140abe0607c35684bec5b761c4e64a31118},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2608.06807. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

We give a new $O(\log n)$ approximation algorithm for Node Weighted Steiner Tree and Node Weighted Steiner Forest. Our algorithm matches the bounds of Klein & Ravi [J. Algorithms '95] which are best possible unless P = NP, but have the advantage that they work in the online setting when the terminal pairs are revealed in random order. To obtain our results, we combine the LearnOrCover framework due to Gupta, Kehne, Levin [FOCS '21] with the Augmented Greedy algorithm of Berman & Coulston [STOC '97] for online edge-weighted Steiner Forest. Neither algorithm suffices on its own, but the analyses dovetail to imply our guarantee. Run offline, the algorithm reduces to a very simple randomized rounding scheme that (in spirit) reduces Node Weighted Steiner Forest to Edge Weighted Steiner Forest, and we hope this idea finds further applications.

Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-08-10 in cs.DS).
Categorie arXiv: Data Structures and Algorithms (cs.DS).
Pagina del lavoro: https://arxiv.org/abs/2608.06807 — 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-10-23T15:08:55.952Z dalla pagina https://arxiv.org/catchup/cs.DS/2026-08-10?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).