Improved Approximation Algorithms for the Expanding Search Problem
Preprint
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 $(2\mathrm{e}+\varepsilon)$-approximation for any $\varepsilon > 0$. For the case that all vertices have unit weight, we provide a $2\mathrm{e}$-approximation. Finally, we provide a PTAS for the case of a Euclidean graph. Previously, for all cases only an $8$-approximation was known.
Keywords
All Related Versions
This publication has 26 references indexed in Scilit:
- The expanding search ratio of a graphDiscrete Applied Mathematics, 2019
- Approximate solutions for expanding search games on general networksAnnals of Operations Research, 2018
- Multiple searchers searching for a randomly distributed immobile target on a unit networkNetworks, 2017
- Emergency path restoration problemsDiscrete Optimization, 2012
- News from the online traveling repairmanTheoretical Computer Science, 2003
- A note on the traveling repairman problemNetworks, 2002
- An improved approximation ratio for the minimum latency problemMathematical Programming, 1998
- Special cases of traveling salesman and repairman problems with time windowsNetworks, 1992
- The delivery man problem on a tree networkAnnals of Operations Research, 1989
- The Steiner problem with edge lengths 1 and 2Information Processing Letters, 1989