Primal–dual algorithms for connected facility location problems

Primal–dual algorithms for connected facility location problems

0.00 Avg rating0 Votes
Article ID: iaor20052966
Country: Germany
Volume: 40
Issue: 4
Start Page Number: 245
End Page Number: 269
Publication Date: Sep 2004
Journal: Algorithmica
Authors: ,
Keywords: heuristics
Abstract:

We consider the Connected Facility Location problem. We are given a graph G = (V, E) with costs {ce} on the edges, a set of facilities FV, and a set of clients DV. Facility i has a facility opening cost fi and client j has dj units of demand. We are also given a parameter M ≥ 1. A solution opens some facilities say F, assigns each client j to an open facility (j), and connects the open facilities by a Steiner tree T. The total cost incurred is i∈Ffi + ∑j∈Ddjci(j)j + M ∑e∈Tce. We want a solution of minimum cost. A special case of this problem is when all opening costs are 0 and facilities may be opened anywhere, i.e., F = V. If we know a facility v that is open, then the problem becomes a special case of the single-sink buy-at-bulk problem with two cable types, also known as the rent-or-buy problem. We give the first primal–dual algorithms for these problems and achieve the best known approximation guarantees. We give an 8.55-approximation algorithm for the connected facility location problem and a 4.55-approximation algorithm for the rent-or-buy problem. Previously the best approximation factors for these problems were 10.66 and 9.001, respectively. Further, these results were not combinatorial – they were obtained by solving an exponential size linear programming relaxation. Our algorithm integrates the primal–dual approaches for the facility location problem and the Steiner tree problem. We also consider the connected k-median problem and give a constant-factor approximation by using our primal–dual algorithm for connected facility location. We generalize our results to an edge capacitated variant of these problems and give a constant-factor approximation for these variants.

Reviews

Required fields are marked *. Your email address will not be published.