1 Search Results for "Grover, Sapna"

Document
DOI: 10.4230/LIPIcs.FSTTCS.2018.23
Constant Factor Approximation Algorithm for Uniform Hard Capacitated Knapsack Median Problem

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

Published in: LIPIcs, Volume 122, 38th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2018)

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.
Cite as

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)

Copy BibTex To Clipboard

@InProceedings{grover_et_al:LIPIcs.FSTTCS.2018.23,
  author =	{Grover, Sapna and Gupta, Neelima and Khuller, Samir and Pancholi, Aditya},
  title =	{{Constant Factor Approximation Algorithm for Uniform Hard Capacitated Knapsack Median Problem}},
  booktitle =	{38th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2018)},
  pages =	{23:1--23:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-093-4},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{122},
  editor =	{Ganguly, Sumit and Pandya, Paritosh},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2018.23},
  URN =		{urn:nbn:de:0030-drops-99224},
  doi =		{10.4230/LIPIcs.FSTTCS.2018.23},
  annote =	{Keywords: Capacitated Knapsack Median, Capacitated k -Facility Location}
}
  • Refine by Author
  • 1 Grover, Sapna
  • 1 Gupta, Neelima
  • 1 Khuller, Samir
  • 1 Pancholi, Aditya

  • Refine by Classification
  • 1 Theory of computation → Facility location and clustering
  • 1 Theory of computation → Rounding techniques

  • Refine by Keyword
  • 1 Capacitated Knapsack Median
  • 1 Capacitated k -Facility Location

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2018

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