Improved Approximation Algorithms for the Expanding Search Problem

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

*Kontaktforfatter

Publikation: Kapitel i bog/rapport/konference-proceedingKonferencebidrag i proceedingsForskningpeer 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.

OriginalsprogEngelsk
Titel31st Annual European Symposium on Algorithms, ESA 2023
RedaktørerInge Li Gortz, Martin Farach-Colton, Simon J. Puglisi, Grzegorz Herman
Antal sider15
ForlagSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
Publikationsdatosep. 2023
Artikelnummer54
ISBN (Elektronisk)9783959772952
DOI
StatusUdgivet - sep. 2023
Begivenhed31st Annual European Symposium on Algorithms, ESA 2023 - Amsterdam, Holland
Varighed: 4. sep. 20236. sep. 2023

Konference

Konference31st Annual European Symposium on Algorithms, ESA 2023
Land/OmrådeHolland
ByAmsterdam
Periode04/09/202306/09/2023
NavnLeibniz International Proceedings in Informatics, LIPIcs
Vol/bind274
ISSN1868-8969

Bibliografisk note

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).

Fingeraftryk

Dyk ned i forskningsemnerne om 'Improved Approximation Algorithms for the Expanding Search Problem'. Sammen danner de et unikt fingeraftryk.

Citationsformater