Improved Approximation Algorithms for the Expanding Search Problem
SIAM Journal on Discrete Mathematics · 31.03.2026 · 40 (1) · 349-373
DOI: 10.1137/25m1759902 ↗Kurz gefasst
Fachartikel in der Zeitschrift SIAM Journal on Discrete Mathematics, online erschienen am 17.03.2026. Verfasst von Svenja M. Griesbach und 3 weiteren Autor:innen. Die Arbeit nennt 44 Literaturangaben. Gefördert von: Berlin Mathematics Research Center, Centro de Modelamiento Matematico, Det Frie Forskningsråd.
Abstract (Originalsprache)
A searcher is tasked with exploring a graph with edge lengths and vertex weights, starting from a designated vertex. Initially, only the starting vertex is considered explored. At each step, the searcher adds an edge to the solution, connecting an unexplored vertex to an explored one. The time required to add an edge equals its length. The objective is to minimize the weighted sum of exploration times for all vertices. We demonstrate that this problem is hard to approximate and present algorithms with improved approximation guarantees. Specifically, we provide a [Formula: see text]-approximation for any [Formula: see text] for the general case. On instances where the vertex weights are binary, we achieve a [Formula: see text]-approximation. Finally, we develop a polynomial-time approximation scheme for Euclidean graphs. Previously, only an 8-approximation was known for all these cases.
Förderung
- Berlin Mathematics Research Center
- Centro de Modelamiento Matematico
- Det Frie Forskningsråd
- Deutsche Forschungsgemeinschaft
- Universität zu Köln
Zitieren
APA
Griesbach, S. M., Hommelsheim, F., Klimm, M., & Schewior, K. (2026). Improved Approximation Algorithms for the Expanding Search Problem. SIAM Journal on Discrete Mathematics, 40(1), 349-373. https://doi.org/10.1137/25m1759902
Vancouver
Griesbach SM, Hommelsheim F, Klimm M, Schewior K. Improved Approximation Algorithms for the Expanding Search Problem. SIAM Journal on Discrete Mathematics. 2026;40(1):349-373. doi:10.1137/25m1759902
BibTeX
@article{Griesbach2026,
author = {Griesbach, Svenja M. and Hommelsheim, Felix and Klimm, Max and Schewior, Kevin},
title = {Improved Approximation Algorithms for the Expanding Search Problem},
journal = {SIAM Journal on Discrete Mathematics},
year = {2026},
volume = {40},
number = {1},
pages = {349--373},
doi = {10.1137/25m1759902}
}
EUVIMED