Improved Approximation Algorithms for the Expanding Search Problem

Svenja M. Griesbach*, Felix Hommelsheim*, Max Klimm*, Kevin Schewior*

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingArticle in proceedingsResearchpeer-review

7 Downloads (Pure)

Abstract

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.

Original languageEnglish
Title of host publication31st Annual European Symposium on Algorithms, ESA 2023
EditorsInge Li Gortz, Martin Farach-Colton, Simon J. Puglisi, Grzegorz Herman
Number of pages15
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
Publication dateSept 2023
Article number54
ISBN (Electronic)9783959772952
DOIs
Publication statusPublished - Sept 2023
Event31st Annual European Symposium on Algorithms, ESA 2023 - Amsterdam, Netherlands
Duration: 4. Sept 20236. Sept 2023

Conference

Conference31st Annual European Symposium on Algorithms, ESA 2023
Country/TerritoryNetherlands
CityAmsterdam
Period04/09/202306/09/2023
SeriesLeibniz International Proceedings in Informatics, LIPIcs
Volume274
ISSN1868-8969

Keywords

  • Approximation Algorithm
  • Expanding Search
  • Graph Exploration
  • Search Problem
  • Traveling Repairperson Problem

Fingerprint

Dive into the research topics of 'Improved Approximation Algorithms for the Expanding Search Problem'. Together they form a unique fingerprint.

Cite this