Document Open Access Logo

Capacitated k-Center Problem with Vertex Weights

Author Aounon Kumar

PDF
Thumbnail PDF

File

LIPIcs.FSTTCS.2016.8.pdf
  • Filesize: 0.5 MB
  • 14 pages

Document Identifiers

Author Details

Aounon Kumar

Cite As Get BibTex

Aounon Kumar. Capacitated k-Center Problem with Vertex Weights. In 36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 65, pp. 8:1-8:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016) https://doi.org/10.4230/LIPIcs.FSTTCS.2016.8

Abstract

We study the capacitated k-center problem with vertex weights. It is a generalization of the well known k-center problem. In this variant each vertex has a weight and a capacity. The assignment cost of a vertex to a center is given by the product of the weight of the vertex and its distance to
the center. The distances are assumed to form a metric. Each center can only serve as many vertices as its capacity. We show an n^{1-epsilon}-approximation hardness for this problem, for any epsilon > 0, where n is the number of vertices in the input. Both the capacitated and the weighted versions of the k-center problem individually can be approximated within a constant factor. Yet the common extension of both the generalizations cannot be approximated efficiently within a constant factor, unless P = NP. This problem, to the best of our knowledge, is the first facility location problem with metric distances known to have a super-constant inapproximability result. The hardness result easily generalizes to versions of the problem that consider the p-norm of the assignment costs (weighted distances) as the objective function. We give n^{1- 1/p - epsilon}-approximation hardness for this problem, for p>1.

We complement the hardness result by showing a simple n-approximation algorithm for this problem. We also give a bi-criteria constant factor approximation algorithm, for the case of uniform capacities, which opens at most 2k centers.

Subject Classification

Keywords
  • approximation hardness
  • k-center
  • gadget reduction

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Hyung-Chan An, Aditya Bhaskara, Chandra Chekuri, Shalmoli Gupta, Vivek Madan, and Ola Svensson. Centrality of trees for capacitated k-center. In Integer Programming and Combinatorial Optimization, pages 52-63. Springer, 2014. Google Scholar
  2. Vijay Arya, Naveen Garg, Rohit Khandekar, Adam Meyerson, Kamesh Munagala, and Vinayaka Pandit. Local search heuristic for k-median and facility location problems. In Proceedings of the Thirty-third Annual ACM Symposium on Theory of Computing, STOC'01, pages 21-29, New York, NY, USA, 2001. ACM. URL: http://dx.doi.org/10.1145/380752.380755.
  3. Manisha Bansal, Naveen Garg, and Neelima Gupta. A 5-approximation for capacitated facility location. In Proceedings of the 20th Annual European Conference on Algorithms, ESA'12, pages 133-144, Berlin, Heidelberg, 2012. Springer-Verlag. URL: http://dx.doi.org/10.1007/978-3-642-33090-2_13.
  4. Jarosław Byrka, Krzysztof Fleszar, Bartosz Rybicki, and Joachim Spoerhase. Bi-factor approximation algorithms for hard capacitated k-median problems. In Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA'15, pages 722-736, Philadelphia, PA, USA, 2015. Society for Industrial and Applied Mathematics. URL: http://dl.acm.org/citation.cfm?id=2722129.2722178.
  5. Jarosław Byrka, Bartosz Rybicki, and Sumedha Uniyal. An approximation algorithm for uniform capacitated k-median problem with (1+ε) capacity violation. In Proceedings of the 18th International Conference on Integer Programming and Combinatorial Optimization (IPCO'16), volume 9682 of LNCS, pages 262-274, New York, NY, USA, 2016. Springer-Verlag New York, Inc. URL: http://dx.doi.org/10.1007/978-3-319-33461-5_22.
  6. Moses Charikar and Sudipto Guha. Improved combinatorial algorithms for the facility location and k-median problems. In Proceedings of the 40th Annual Symposium on Foundations of Computer Science, FOCS'99, pages 378-, Washington, DC, USA, 1999. IEEE Computer Society. URL: http://dl.acm.org/citation.cfm?id=795665.796483.
  7. Moses Charikar, Sudipto Guha, Éva Tardos, and David B. Shmoys. A constant-factor approximation algorithm for the k-median problem (extended abstract). In Proceedings of the Thirty-first Annual ACM Symposium on Theory of Computing, STOC'99, pages 1-10, New York, NY, USA, 1999. ACM. URL: http://dx.doi.org/10.1145/301250.301257.
  8. A. Fabián Chudak and P. David Williamson. Improved approximation algorithms for capacitated facility location problems. Mathematical Programming, 102(2):207-222, 2005. URL: http://dx.doi.org/10.1007/s10107-004-0524-9.
  9. Julia Chuzhoy and Yuval Rabani. Approximating k-median with non-uniform capacities. In In SODA'05, pages 952-958, 2005. Google Scholar
  10. Marek Cygan, MohammadTaghi Hajiaghayi, and Samir Khuller. Lp rounding for k-centers with non-uniform hard capacities. In Foundations of Computer Science (FOCS), 2012 IEEE 53rd Annual Symposium on, pages 273-282. IEEE, 2012. Google Scholar
  11. Michael R. Garey and David S. Johnson. Computers and Intractability; A Guide to the Theory of NP-Completeness. W. H. Freeman &Co., New York, NY, USA, 1990. Google Scholar
  12. Teofilo F. Gonzalez. Clustering to minimize the maximum intercluster distance. Theoretical Computer Science, 38:293-306, 1985. URL: http://dx.doi.org/10.1016/0304-3975(85)90224-5.
  13. Dorit S Hochbaum and David B Shmoys. A best possible heuristic for the k-center problem. Mathematics of operations research, 10(2):180-184, 1985. Google Scholar
  14. Wen-Lian Hsu and George L. Nemhauser. Easy and hard bottleneck location problems. Discrete Applied Mathematics, 1(3):209-215, 1979. URL: http://dx.doi.org/10.1016/0166-218X(79)90044-1.
  15. Kamal Jain and Vijay V. Vazirani. Approximation algorithms for metric facility location and k-median problems using the primal-dual schema and lagrangian relaxation. J. ACM, 48(2):274-296, March 2001. URL: http://dx.doi.org/10.1145/375827.375845.
  16. Samir Khuller and Yoram J. Sussmann. The capacitated k-center problem. In In Proceedings of the 4th Annual European Symposium on Algorithms, Lecture Notes in Computer Science 1136, pages 152-166. Springer, 1996. Google Scholar
  17. Madhukar R. Korupolu, C.Greg Plaxton, and Rajmohan Rajaraman. Analysis of a local search heuristic for facility location problems. Journal of Algorithms, 37(1):146-188, 2000. URL: http://dx.doi.org/10.1006/jagm.2000.1100.
  18. Shi Li. On uniform capacitated k-median beyond the natural lp relaxation. In Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA'15, pages 696-707, Philadelphia, PA, USA, 2015. Society for Industrial and Applied Mathematics. URL: http://dl.acm.org/citation.cfm?id=2722129.2722176.
  19. Martin Pal, Eva Tardos, and Tom Wexler. Facility location with nonuniform hard capacities. In Proceedings of the 42nd IEEE Symposium on the Foundations of Computer Science, pages 329-338, 2001. Google Scholar
  20. Qingzhou Wang and Kam Hoi Cheng. A heuristic algorithm for the k-center problem with vertex weight. In Proceedings of the International Symposium on Algorithms, SIGAL'90, pages 388-396, New York, NY, USA, 1990. Springer-Verlag New York, Inc. URL: http://dl.acm.org/citation.cfm?id=88307.88459.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact