Improved Approximation Algorithms for the Expanding Search Problem
- 17 March 2026
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Discrete Mathematics
- Vol. 40 (1) , 349-373
Abstract
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.Keywords
All Related Versions
Funding Information
- Berlin Mathematics Research Center (EXC-2046/1)
- Berlin Mathematics Research Center (390685689)
- Centro de Modelamiento Matemático (FB210005)
- Danmarks Frie Forskningsfond (DFF-0135-00018B)
- Deutsche Forschungsgemeinschaft
- Universität zu Köln
This publication has 39 references indexed in Scilit:
- Multiple searchers searching for a randomly distributed immobile target on a unit networkNetworks, 2017
- Search Theory2013
- Hyperbolic DovetailingLecture Notes in Computer Science, 2009
- The Directed Minimum Latency Problem2008
- Maximum Coverage Problem with Group Budget Constraints and Applications2004
- A note on the traveling repairman problemNetworks, 2002
- The Minimum Latency Problem Is NP-Hard for Weighted Trees2002
- An improved approximation ratio for the minimum latency problemMathematical Programming, 1998
- Searching a fixed graph1996
- Special cases of traveling salesman and repairman problems with time windowsNetworks, 1992