Improved 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 c, on the edges, a set of facilities F subset of V, a set of demands, i.e., clients D subset of 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 subset of F, assign each demand j to some open facility i(j) E F and connect all open facilities using a Steiner tree T such that the total cost, which is Sigma(i epsilon F) f(i) + Sigma(j epsilon D) d(j)c(i(j)j) + M Sigma(e epsilon T) C-e, is minimized. We give an improved primal-dual 6.55-approximation algorithm for the ConFL problem which improves the Swamy and Kumar's primal-dual 8.55-approximation algorithm [1].