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

Abstract

In the connected facility location (ConFL) problem, we are given a graph G = (V, E) with nonnegative edge cost c(e) 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. F, assign each demand j to some open facility i(j) is an element of F and connect all open facilities using a Steiner tree T such that the total cost, which is Sigma(i is an element of F) f(i) + Sigma(j is an element of D) d(j) c(i) ((j)) (j) + M Sigma(e is an element of T) 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).