TY - GEN

T1 - Improved Approximation Algorithms for the Expanding Search Problem

AU - Griesbach, Svenja M.

AU - Hommelsheim, Felix

AU - Klimm, Max

AU - Schewior, Kevin

N1 - Funding Information:
Funding Svenja M. Griesbach: Supported by Deutsche Forschungsgemeinschaft under Germany’s Excellence Strategy, Berlin Mathematics Research Center (grant EXC-2046/1, Project 39068689) and HYPATIA.SCIENCE (Department of Mathematics and Computer Science, University of Cologne). Max Klimm: Supported by Deutsche Forschungsgemeinschaft under Germany’s Excellence Strategy, Berlin Mathematics Research Center (grant EXC-2046/1, Project 390685689). Kevin Schewior: Supported in part by the Independent Research Fund Denmark, Natural Sciences (grant DFF-0135-00018B).

PY - 2023/9

Y1 - 2023/9

N2 - A searcher faces a graph with edge lengths and vertex weights, initially having explored only a given starting vertex. In each step, the searcher adds an edge to the solution that connects an unexplored vertex to an explored vertex. This requires an amount of time equal to the edge length. The goal is to minimize the weighted sum of the exploration times over all vertices. We show that this problem is hard to approximate and provide algorithms with improved approximation guarantees. For the general case, we give a (2e + ε)-approximation for any ε > 0. For the case that all vertices have unit weight, we provide a 2e-approximation. Finally, we provide a PTAS for the case of a Euclidean graph. Previously, for all cases only an 8-approximation was known.

AB - A searcher faces a graph with edge lengths and vertex weights, initially having explored only a given starting vertex. In each step, the searcher adds an edge to the solution that connects an unexplored vertex to an explored vertex. This requires an amount of time equal to the edge length. The goal is to minimize the weighted sum of the exploration times over all vertices. We show that this problem is hard to approximate and provide algorithms with improved approximation guarantees. For the general case, we give a (2e + ε)-approximation for any ε > 0. For the case that all vertices have unit weight, we provide a 2e-approximation. Finally, we provide a PTAS for the case of a Euclidean graph. Previously, for all cases only an 8-approximation was known.

KW - Approximation Algorithm

KW - Expanding Search

KW - Graph Exploration

KW - Search Problem

KW - Traveling Repairperson Problem

U2 - 10.4230/LIPIcs.ESA.2023.54

DO - 10.4230/LIPIcs.ESA.2023.54

M3 - Article in proceedings

AN - SCOPUS:85173433939

T3 - Leibniz International Proceedings in Informatics, LIPIcs

BT - 31st Annual European Symposium on Algorithms, ESA 2023

A2 - Li Gortz, Inge

A2 - Farach-Colton, Martin

A2 - Puglisi, Simon J.

A2 - Herman, Grzegorz

PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing

T2 - 31st Annual European Symposium on Algorithms, ESA 2023

Y2 - 4 September 2023 through 6 September 2023

ER -