Abstract
We present two local search algorithms for the k-median and k-facility location problems with linear penalties (k-MLP and k-FLPLP), two extensions of the classical k-median and k-facility location problems respectively. We show that the approximation ratios of these two algorithms are \(3+2/p+\epsilon \) for the k-MLP, and \(2 + 1/p + \sqrt{3+ 2/p+ 1/p^2} + \epsilon \) for the k-FLPLP, respectively, where \(p \in {\mathbb {Z}}_+\) is a parameter of the algorithms and \(\epsilon >0\) is a positive number. In particular, the \((3+2/p+\epsilon )\)-approximation improves the best known 4-approximation for the k-MLP for any \(p>2\).
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Archer, A., Bateni, M., Hajiaghayi, M., Karloff, H.: Improved approximation algorithms for prize-collecting Steiner tree and TSP. SIAM J. Comput. 40, 309–332 (2011)
Arya, V., Garg, N., Khandekar, R., Meyerson, A., Munagala, K., Pandit, V.: Local search heuristics for \(k\)-median and facility location problems. SIAM J. Comput. 33, 544–562 (2004)
Bienstock, D., Goemans, M.X., Simchi-Levi, D., Williamson, D.: A note on the prize collecting traveling salesman problem. Math. Program. 59, 413–420 (1993)
Bartal, Y., Leonardi, S., Marchetti-Spaccamela, A., Sgall, J., Stougie, L.: Multiprocessor scheduling with rejection. SIAM J. Discrete Math. 13, 64–78 (2000)
Byrka, J., Pensyl, T., Rybicki, B., Srinivasan, A., Trinh, K.: An improved approximation for \(k\)-median, and positive correlation in budgeted optimization. In: Proceedings of the 26th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 737–756 (2015)
Charikar, M., Guha, S., Tardos, É., Shmoys D.B.: A constant-factor approximation algorithm for the \(k\)-median problem. In: Proceedings of the 31st Annual ACM Symposium on Theory of Computing, pp. 1–10 (1999)
Charikar, M., Khuller, S., Mount, D.M., Narasimhan, G.: Algorithms for facility location problems with outliers. In: Proceedings of the 20th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 642–651 (2001)
Gupta, N., Gupta, S.: Approximation algorithms for capacitated facility location problem with penalties (2014). ArXiv: 1408.4944
Czumaj, A., Mehlhorn, K., Pitts, A., Wattenhofer, R.: A dependent LP-rounding approach for the k-median problem. In: Charikar, M., Li, S. (eds.) ICALP 2012. LNCS, vol. 7391, pp. 194–205. Springer, Heidelberg (2012)
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)
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)
Li, Y., Du, D., Xiu, N., Xu, D.: Improved approximation algorithms for the facility location problems with linear/submodular penalties. Algorithmica 73, 460–482 (2015)
Shabtay, D., Gaspar, N., Kaspi, M.: A survey on offline scheduling with rejection. J. Sched. 16, 3–28 (2013)
Zhang, P.: A new approximation algorithm for the \(k\)-facility location problem. Theor. Comput. Sci. 384, 126–135 (2007)
Acknowledgements
The research of the first author is supported by Collaborative Innovation Center on Beijing Society-Buliding and Social Governance. The second author’s research is supported by NSFC (Nos. 11371001 and 11531014). The third author’s research is supported by the Natural Sciences and Engineering Research Council of Canada (NSERC) grant 283106. The fourth author’s research is supported by NSFC (No. 11501412).
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2015 Springer International Publishing Switzerland
About this paper
Cite this paper
Wang, Y., Xu, D., Du, D., Wu, C. (2015). Local Search Algorithms for k-Median and k-Facility Location Problems with Linear Penalties. In: Lu, Z., Kim, D., Wu, W., Li, W., Du, DZ. (eds) Combinatorial Optimization and Applications. Lecture Notes in Computer Science(), vol 9486. Springer, Cham. https://doi.org/10.1007/978-3-319-26626-8_5
Download citation
DOI: https://doi.org/10.1007/978-3-319-26626-8_5
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-26625-1
Online ISBN: 978-3-319-26626-8
eBook Packages: Computer ScienceComputer Science (R0)