A unified dual-fitting approximation algorithm for the facility location problems with linear/submodular penalties
In this paper, we study two variants of the classical facility location problem, namely, the facility location problem with linear penalties (FLPLP) and the facility location problem with submodular penalties (FLPSP), respectively. We give a unified dual-fitting based approximation algorithm for these two problems, yielding approximation ratios 2 and 3 respectively.
approximation algorithm facility location problem linear programming submodular function