A 6.55 factor primal-dual approximation algorithm for the connected facility location problem

In the connected facility location (ConFL) problem, we are given a graph G=(V,E) with nonnegative edge cost ce on the edges, a set of facilities F⊆V, a set of demands (i.e., clients) 𝒟⊆V, and a parameter M≥1. Each facility i has a nonnegative opening cost f i and each client j has d j units of demand. Our objective is to open some facilities, say F⊆F, assign each demand j to some open facility i(j)∈F and connect all open facilities using a Steiner tree T such that the total cost, which is $\underset{i\in F}{\Sigma }{f}_i+\underset{j\in 𝒟}{\Sigma }{d}_j{c}_{i\left(j\right)j}+M\underset{e\in T}{\Sigma }{c}_e$ , is minimized. We present a primal-dual 6.55-approximation algorithm for the ConFL problem which improves the previous primal-dual 8.55-approximation algorithm given by Swamy and Kumar (Algorithmica 40:245–269, 2004).