A Primal‐Dual Approximation Algorithm for the Facility Location Problem with Submodular Penalties

A Primal‐Dual Approximation Algorithm for the Facility Location Problem with Submodular Penalties

0.00 Avg rating0 Votes
Article ID: iaor2012672
Volume: 63
Issue: 1
Start Page Number: 191
End Page Number: 200
Publication Date: Jun 2012
Journal: Algorithmica
Authors: , ,
Keywords: combinatorial optimization, programming: linear, programming: integer, heuristics
Abstract:

We consider the facility location problem with submodular penalties (FLPSP), introduced by Hayrapetyan et al. (2005), who presented a 2.50-approximation algorithm that is non-combinatorial because this algorithm has to solve the LP-relaxation of an integer program with exponential number of variables. The only known polynomial algorithm for this exponential LP is via the ellipsoid algorithm as the corresponding separation problem for its dual program can be solved in polynomial time. By exploring the properties of the submodular function, we offer a primal-dual 3-approximation combinatorial algorithm for this problem.

Reviews

Required fields are marked *. Your email address will not be published.