Document Open Access Logo

Constant Factor Approximation Algorithm for Uniform Hard Capacitated Knapsack Median Problem

Authors Sapna Grover, Neelima Gupta, Samir Khuller, Aditya Pancholi

PDF
Thumbnail PDF

File

LIPIcs.FSTTCS.2018.23.pdf
  • Filesize: 0.78 MB
  • 22 pages

Document Identifiers

Author Details

Sapna Grover
  • Department of Computer Science, University of Delhi, Delhi, India
Neelima Gupta
  • Department of Computer Science, University of Delhi, Delhi, India
Samir Khuller
  • Department of Computer Science, University of Maryland, College Park, MD 20742, USA
Aditya Pancholi
  • Department of Computer Science, University of Delhi, Delhi, India

Cite AsGet BibTex

Sapna Grover, Neelima Gupta, Samir Khuller, and Aditya Pancholi. Constant Factor Approximation Algorithm for Uniform Hard Capacitated Knapsack Median Problem. In 38th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 122, pp. 23:1-23:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
https://doi.org/10.4230/LIPIcs.FSTTCS.2018.23

Abstract

In this paper, we give the first constant factor approximation algorithm for capacitated knapsack median problem (CKnM) for hard uniform capacities, violating the budget by a factor of 1+epsilon and capacities by a 2+epsilon factor. To the best of our knowledge, no constant factor approximation is known for the problem even with capacity/budget/both violations. Even for the uncapacitated variant of the problem, the natural LP is known to have an unbounded integrality gap even after adding the covering inequalities to strengthen the LP. Our techniques for CKnM provide two types of results for the capacitated k-facility location problem. We present an O(1/epsilon^2) factor approximation for the problem, violating capacities by (2+epsilon). Another result is an O(1/epsilon) factor approximation, violating the capacities by a factor of at most (1 + epsilon) using at most 2k facilities for a fixed epsilon>0. As a by-product, a constant factor approximation algorithm for capacitated facility location problem with uniform capacities is presented, violating the capacities by (1 + epsilon) factor. Though constant factor results are known for the problem without violating the capacities, the result is interesting as it is obtained by rounding the solution to the natural LP, which is known to have an unbounded integrality gap without violating the capacities. Thus, we achieve the best possible from the natural LP for the problem. The result shows that the natural LP is not too bad.

Subject Classification

ACM Subject Classification
  • Theory of computation → Facility location and clustering
  • Theory of computation → Rounding techniques
Keywords
  • Capacitated Knapsack Median
  • Capacitated k -Facility Location

Metrics

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

References

  1. Karen Aardal, Pieter L. van den Berg, Dion Gijswijt, and Shanfei Li. Approximation algorithms for hard capacitated k-facility location problems. EJOR, 242(2):358-368, 2015. URL: http://dx.doi.org/10.1016/j.ejor.2014.10.011.
  2. Ankit Aggarwal, Anand Louis, Manisha Bansal, Naveen Garg, Neelima Gupta, Shubham Gupta, and Surabhi Jain. A 3-approximation algorithm for the facility location problem with uniform capacities. Journal of Mathematical Programming, 141(1-2):527-547, 2013. URL: http://dx.doi.org/10.1007/s10107-012-0565-4.
  3. Hyung-Chan An, Aditya Bhaskara, Chandra Chekuri, Shalmoli Gupta, Vivek Madan, and Ola Svensson. Centrality of trees for capacitated k-center. Math. Program., 154(1-2):29-53, 2015. URL: http://dx.doi.org/10.1007/s10107-014-0857-y.
  4. Hyung-Chan An, Mohit Singh, and Ola Svensson. LP-Based Algorithms for Capacitated Facility Location. In FOCS, 2014, pages 256-265, 2014. URL: http://dx.doi.org/10.1109/FOCS.2014.35.
  5. Manisha Bansal, Naveen Garg, and Neelima Gupta. A 5-Approximation for Capacitated Facility Location. In Algorithms - ESA 2012 - 20th Annual European Symposium, Ljubljana, Slovenia, September 10-12, 2012. Proceedings, pages 133-144, 2012. URL: http://dx.doi.org/10.1007/978-3-642-33090-2_13.
  6. Jaroslaw Byrka, Krzysztof Fleszar, Bartosz Rybicki, and Joachim Spoerhase. Bi-Factor Approximation Algorithms for Hard Capacitated k-Median Problems. In SODA 2015, pages 722-736, 2015. URL: http://dx.doi.org/10.1137/1.9781611973730.49.
  7. Jaroslaw Byrka, Thomas Pensyl, Bartosz Rybicki, Joachim Spoerhase, Aravind Srinivasan, and Khoa Trinh. An Improved Approximation Algorithm for Knapsack Median Using Sparsification. In ESA 2015, pages 275-287, 2015. URL: http://dx.doi.org/10.1007/978-3-662-48350-3_24.
  8. Jaroslaw Byrka, Bartosz Rybicki, and Sumedha Uniyal. An Approximation Algorithm for Uniform Capacitated k-Median Problem with (1 + ε) Capacity Violation. In Integer Programming and Combinatorial Optimization - 18th International Conference, IPCO 2016, Liège, Belgium, June 1-3, 2016, Proceedings, pages 262-274, 2016. URL: http://dx.doi.org/10.1007/978-3-319-33461-5_22.
  9. Moses Charikar and Sudipto Guha. Improved combinatorial algorithms for the facility location and k-median problems. In Proceedings of the 40th Annual IEEE Symposium on Foundations of Computer Science (FOCS), New York, NY, USA, pages 378-388, 1999. Google Scholar
  10. Moses Charikar and Sudipto Guha. Improved combinatorial algorithms for facility location problems. SIAM Journal on Computing, 34(4):803-824, 2005. Google Scholar
  11. Moses Charikar, Sudipto Guha, Éva Tardos, and David B. Shmoys. A Constant-Factor Approximation Algorithm for the k-Median Problem (Extended Abstract). In STOC, 1999, pages 1-10, 1999. URL: http://dx.doi.org/10.1145/301250.301257.
  12. Moses Charikar and Shi Li. A Dependent LP-Rounding Approach for the k-Median Problem. In ICALP 2012, pages 194-205, 2012. URL: http://dx.doi.org/10.1007/978-3-642-31594-7_17.
  13. Marek Cygan, MohammadTaghi Hajiaghayi, and Samir Khuller. LP rounding for k-centers with non-uniform hard capacities. In 53rd Annual IEEE Symposium on Foundations of Computer Science, FOCS 2012, New Brunswick, NJ, USA, October 20-23, 2012, pages 273-282, 2012. URL: http://dx.doi.org/10.1109/FOCS.2012.63.
  14. H. Gökalp Demirci and Shi Li. Constant Approximation for Capacitated k-Median with (1 + ε) Capacity Violation. In 43rd ICALP 2016, July 11-15, 2016, Rome, Italy, pages 73:1-73:14, 2016. Google Scholar
  15. Samir Khuller and Yoram J. Sussmann. The Capacitated K-Center Problem. SIAM J. Discrete Math., 13(3):403-418, 2000. URL: http://dx.doi.org/10.1137/S0895480197329776.
  16. 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/http://dx.doi.org/10.1006/jagm.2000.1100.
  17. Ravishankar Krishnaswamy, Amit Kumar, Viswanath Nagarajan, Yogish Sabharwal, and Barna Saha. The Matroid Median Problem. In SODA, 2011, pages 1117-1130, 2011. URL: http://dx.doi.org/10.1137/1.9781611973082.84.
  18. Ravishankar Krishnaswamy, Shi Li, and Sai Sandeep. Constant approximation for k-median and k-means with outliers via iterative rounding. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2018, Los Angeles, CA, USA, June 25-29, 2018, pages 646-659, 2018. URL: http://dx.doi.org/10.1145/3188745.3188882.
  19. Amit Kumar. Constant Factor Approximation Algorithm for the Knapsack Median Problem. In SODA, 2012, pages 824-832. SIAM, 2012. URL: http://dl.acm.org/citation.cfm?id=2095116.2095182.
  20. Retsef Levi, David B. Shmoys, and Chaitanya Swamy. LP-based approximation algorithms for capacitated facility location. Journal of Mathematical Programming, 131(1-2):365-379, 2012. URL: http://dx.doi.org/10.1007/s10107-010-0380-8.
  21. Shanfei Li. An Improved Approximation Algorithm for the Hard Uniform Capacitated k-median Problem. In Klaus Jansen, José D. P. Rolim, Nikhil R. Devanur, and Cristopher Moore, editors, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014), Germany, volume 28 of Leibniz International Proceedings in Informatics (LIPIcs), pages 325-338. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2014. URL: http://dx.doi.org/10.4230/LIPIcs.APPROX-RANDOM.2014.325.
  22. 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 2015, San Diego, CA, USA, January 4-6, 2015, pages 696-707, 2015. URL: http://dx.doi.org/10.1137/1.9781611973730.47.
  23. Shi Li. Approximating capacitated k-median with (1 + ε)k open facilities. In Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016, Arlington, VA, USA, January 10-12, 2016, pages 786-796, 2016. URL: http://dx.doi.org/10.1137/1.9781611974331.ch56.
  24. Jyh-Han Lin and Jeffrey Scott Vitter. epsilon-Approximations with Minimum Packing Constraint Violation (Extended Abstract). In Proceedings of the 24th Annual ACM Symposium on Theory of Computing, May 4-6, 1992, Victoria, British Columbia, Canada, pages 771-782, 1992. URL: http://dx.doi.org/10.1145/129712.129787.
  25. David B. Shmoys, Éva Tardos, and Karen Aardal. Approximation Algorithms for Facility Location Problems (Extended Abstract). In Proceedings of the Twenty-Ninth Annual ACM Symposium on the Theory of Computing, El Paso, Texas, USA,, pages 265-274, 1997. URL: http://dx.doi.org/10.1145/258533.258600.
  26. Chaitanya Swamy. Improved Approximation Algorithms for Matroid and Knapsack Median Problems and Applications. In APPROX/RANDOM, 2014, pages 403-418, 2014. URL: http://dx.doi.org/10.4230/LIPIcs.APPROX-RANDOM.2014.403.
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 Imprint Privacy Contact