A Primal-Dual Approximation Algorithm for the Facility Location Problem with Submodular Penalties |
| |
| Authors: | Donglei Du Ruixing Lu Dachuan Xu |
| |
| Affiliation: | 1. Faculty of Business Administration, University of New Brunswick, Fredericton, NB, E3B 5A3, Canada
2. Department of Applied Mathematics, Beijing University of Technology, 100 Pingleyuan, Chaoyang District, Beijing, 100124, P.R. China
|
| |
| Abstract: | We consider the facility location problem with submodular penalties (FLPSP), introduced by Hayrapetyan et?al. (Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 933–942, 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. |
| |
| Keywords: | |
| 本文献已被 SpringerLink 等数据库收录！ |
|
