2026-07-25T03:04:22Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:18707 2024-03-06T11:02:31Z ddc:004 open_access

Improved Approximation Algorithms for the Expanding Search Problem Griesbach, Svenja M. Hommelsheim, Felix Klimm, Max Schewior, Kevin Approximation Algorithm Expanding Search Search Problem Graph Exploration Traveling Repairperson Problem 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Svenja M. Griesbach and Felix Hommelsheim and Max Klimm and Kevin Schewior 2023 Is Part Of LIPIcs, Volume 274, 31st Annual European Symposium on Algorithms (ESA 2023) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2023.54 urn:nbn:de:0030-drops-187073 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2023.54 eng https://creativecommons.org/licenses/by/4.0/legalcode