Continuous facility location on graphs

Mathematical Programming, vol. 192, pp. 207–227

Abstract

Abstract We study a continuous facility location problem on undirected graphs where all edges have unit length and where the facilities may be positioned on the vertices as well as on interior points of the edges. The goal is to cover the entire graph with a minimum number of facilities with covering range $$\delta >0$$ δ > 0 . In other words, we want to position as few facilities as possible subject to the condition that every point on every edge is at distance at most $$\delta $$ δ from one of these facilities. We investigate this covering problem in terms of the rational parameter $$\delta $$ δ . We prove that the problem is polynomially solvable whenever $$\delta $$ δ is a unit fraction, and that the problem is NP-hard for all non unit fractions $$\delta $$ δ . We also analyze the parametrized complexity with the solution size as parameter: The resulting problem is fixed parameter tractable for $$\delta <3/2$$ δ < 3 / 2 , and it is W[2]-hard for $$\delta \ge 3/2$$ δ ≥ 3 / 2 .

Authors 3

1. Tim A. Hartmann Aachen Department of Computer Science

   RWTH Aachen University

   Affiliation as printed

   Department of Computer Science, RWTH Aachen, Aachen, Germany

2. Stefan Lendl

   Graz University of Technology

   Affiliation as printed

   Institute of Discrete Mathematics, TU Graz, Graz, Austria

3. Gerhard J. Woeginger corresponding Aachen Department of Computer Science

   RWTH Aachen University

   Affiliation as printed

   Department of Computer Science, RWTH Aachen, Aachen, Germany