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.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Aardal, K.I., Chudak, F.A., Shmoys, D.B.: A 3-approximation algorithm for the k-level uncapacitated facility location problem. Inf. Process. Lett. 72, 161–167 (1999)
Ageev, A., Ye, Y., Zhang, J.: Improved combinatorial approximation algorithms for the k-level facility location problem. SIAM J. Discrete Math. 18, 207–217 (2003)
Byrka, J., Aardal, K.I.: An optimal bifactor approximation algorithm for the metric uncapacitated facility location problem. SIAM J. Comput. 39, 2212–2231 (2010)
Charikar, M., Guha, S.: Improved combinatorial algorithms for facility location and k-median problems. In: Proceedings of the Fortieth Annual IEEE Symposium on Foundations of Computer Science (FOCS), pp. 378–388 (1999)
Charikar, M., Khuller, S., Mount, D.M., Naraasimban, G.: Algorithms for facility location problems with outliers. In: Proceedings of the Twelfth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 642–651 (2001)
Chudak, F.A., Nagano, K.: Efficient solutions to relaxations of combinatorial problems with submodular penalties via the Lovasz extension and non-smooth convex optimization. In: Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 79–88 (2007)
Chudak, F.A., Shmoys, D.B.: Improved approximation algorithms for the uncapacitated facility location problem. SIAM J. Comput. 33, 1–25 (2003)
Du, D., Wang, X., Xu, D.: An approximation algorithm for the k-level capacitated facility location problem. J. Comb. Optim. 20, 361–368 (2010)
Fleischer, L., Iwata, S.: A push-relabel framework for submodular function minimization and applications to parametric optimization. Discrete Appl. Math. 131, 311–322 (2003)
Guha, S., Khuller, S.: Greedy strikes back: improved facility location algorithms. J. Algorithms 31, 228–248 (1999)
Hayrapetyan, A., Swamy, C., Tardos, E.: Network design for information networks. In: Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 933–942 (2005)
Jain, K., Vazirani, V.V.: Approximation algorithms for metric facility location and k-median problems using the primal-dual schema and Lagrangian relaxation. J. ACM 48, 274–296 (2001)
Jain, K., Mahdian, M., Markakis, E., Saberi, A., Vazirani, V.V.: Greedy facility location algorithms analyzed using dual fitting with factor-revealing LP. J. ACM 50, 795–824 (2003)
Korupolu, M.R., Plaxton, C.G., Rajaraman, R.: Analysis of a local search heuristic for facility location problems. J. Algorithms 37, 146–188 (2000)
Mahdian, M., Ye, Y., Zhang, J.: Approximation algorithms for metric facility location problems. SIAM J. Comput. 36, 411–432 (2006)
Shmoys, D.B., Tardos, E., Aardal, K.I.: Approximation algorithms for facility location problems (extended abstract). In: Proceedings of the Twenty-Ninth Annual ACM Symposium on Theory of Computing (STOC), pp. 265–274 (1997)
Sviridenko, M.: An improved approximation algorithm for the metric uncapacitated facility location problem. In: Proceedings of the Ninth Integer Programming and Combinatorial Optimization (IPCO), pp. 240–257 (2002)
Xu, D., Du, D.: The k-level facility location game. Oper. Res. Lett. 34, 421–426 (2006)
Xu, G., Xu, J.: An LP rounding algorithm for approximating uncapacitated facility location problem with penalties. Inf. Process. Lett. 94, 119–123 (2005)
Xu, G., Xu, J.: An improved approximation algorithm for uncapacitated facility location problem with penalties. J. Comb. Optim. 17, 424–436 (2009)
Xu, D., Zhang, S.: Approximation algorithm for facility location with service installation costs. Oper. Res. Lett. 36, 46–50 (2008)
Zhang, J.: Approximating the two-level facility location problem via a quasi-greedy approach. Math. Program. 108, 159–176 (2006)
Zhang, J., Chen, B., Ye, Y.: A multiexchange local search algorithm for the capacitated facility location problem. Math. Oper. Res. 30, 389–403 (2005)
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Du, D., Lu, R. & Xu, D. A Primal-Dual Approximation Algorithm for the Facility Location Problem with Submodular Penalties. Algorithmica 63, 191–200 (2012). https://doi.org/10.1007/s00453-011-9526-1
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00453-011-9526-1