Constant factor approximation algorithm for uniform hard capacitated knapsack median problem

Sapna Grover, Neelima Gupta, Samir Khuller, Aditya Pancholi

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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 + ∊ and capacities by a 2 + ∊ 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/∊2) factor approximation for the problem, violating capacities by (2+∊). Another result is an O(1/∊) factor approximation, violating the capacities by a factor of at most (1+∊) using at most 2k facilities for a fixed ∊ > 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 + ∊) 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.

Original languageEnglish (US)
Title of host publication38th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2018
EditorsSumit Ganguly, Paritosh Pandya
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
ISBN (Electronic)9783959770934
DOIs
StatePublished - Dec 2018
Externally publishedYes
Event38th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2018 - Ahmedabad, India
Duration: Dec 11 2018Dec 13 2018

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
Volume122
ISSN (Print)1868-8969

Conference

Conference38th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2018
CountryIndia
CityAhmedabad
Period12/11/1812/13/18

Keywords

  • Capacitated k-facility location
  • Capacitated knapsack median

ASJC Scopus subject areas

  • Software

Fingerprint Dive into the research topics of 'Constant factor approximation algorithm for uniform hard capacitated knapsack median problem'. Together they form a unique fingerprint.

  • Cite this

    Grover, S., Gupta, N., Khuller, S., & Pancholi, A. (2018). Constant factor approximation algorithm for uniform hard capacitated knapsack median problem. In S. Ganguly, & P. Pandya (Eds.), 38th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2018 [23] (Leibniz International Proceedings in Informatics, LIPIcs; Vol. 122). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. https://doi.org/10.4230/LIPIcs.FSTTCS.2018.23