Approximating δ-Covering

Summary

delta-Covering, for some covering range delta>0, is a continuous facility location problem on undirected graphs where all edges have unit length. The facilities may be positioned on the vertices as well as on the interior of the edges. The goal is to position as few facilities as possible such that every point on every edge has distance at most delta to one of these facilities. For large delta, the problem is similar to dominating set, which is hard to approximate, while for small delta, say close to 1, the problem is similar to vertex cover. In fact, as shown by Hartmann et al. [Math. Program. 22], delta-Covering for all unit-fractions delta is polynomial time solvable, while for all over delta the problem NP-hard. We study the approximability of delta-Covering for every covering range delta>0. For delta >= 3/2, the problem is log APX-hard, and allows a O(log n) approximation. For every delta < 3/2, there is a constant factor approximation of a minimum delta-cover (and is APX-hard when delta is not a unit-fraction). We further study the dependency of the approximation ratio on the covering range delta < 3/2. By providing several polynomial time approximation algorithms and lower bounds under the Unique Game Conjecture, we narrow the possible approximation ratio, especially for delta close to the polynomial time solvable cases.