Improved Primal-Dual ApproximationAlgorithm 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_e on the edges, a set of facilities (F) (C) V, a set of demands, i.e., clients D (C) V, and a parameter M ≥ 1. Each facility i has a nonnegative opening cost f_i and each client j has dj units of demand. Our objective is to open some facilities, say F (C) (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 ∑_(i∈F)f_i + ∑_(j∈D) d_jC_(i(j)j) + M∑_(e∈T)c_e 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.