Approximation algorithms for connected facility location problems

Abstract

We study Connected Facility Location problems. We are given a connected graph G = (V, E) with nonnegative edge cost c(e) for each edge e epsilon E, a set of clients D subset of V such that each client j epsilon D has positive demand d(j) and a set of facilities F subset of V each has nonnegative opening cost f(i) and capacity to serve all client demands. The objective is to open a subset of facilities, say (F) over cap, to assign each client j epsilon D to exactly one open facility i(j) and to connect all open facilities by a Steiner tree T such that the cost Sigma(i epsilon(F) over cap) f(i) + Sigma (j epsilon D) d(j)c(i(j)j) + M Sigma(e epsilon T) c(e) is minimized for a given input parameter M >= 1. We propose a LP-rounding based 8.29 approximation algorithm which improves the previous bound 8.55 (Swamy and Kumar in Algorithmica, 40: 245-269, 2004). We also consider the problem when opening cost of all facilities are equal. In this case we give a 7.0 approximation algorithm.