Improved approximation algorithm for connected facility locatin problems

Abstract

We study the Connected Facility Location problems. We are given a connected weighted graph G = (V,E) with non-negative edge cost $C_e$ for each edge $e \in E$, a set of clients $D \subseteq V$ such that each client $j \in D$ has positive demand $d_j$ and a set of facilities $F \sebseteq V$ each has non-negative opening cost $f_i$ and capacity to serve all client demands. The objective is to open a subset of facilities, say $\^{F}$, connect each client $j \in D$ to exactly one open facility i(j) and to connect all open facilities by a Steiner tree T such that the cost $\sum_{i \in \^{F}}f_i + \sum_{j \in D}d_jc_i(j)j + M \sum_{e \in T}c_e$ is minimized, where $M \geq 1$ be an input parameter. We propose a LP-rounding based 8.29 approximation algorithm which improves the previous bound 8.55. We also consider the problem when opening cost of all facilities are equal. In this case we give a 7.0 approximation algorithm.