License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.FSTTCS.2013.275
URN: urn:nbn:de:0030-drops-43795
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2013/4379/
Go to the corresponding LIPIcs Volume Portal

Chakaravarthy, Venkatesan T. ; Choudhury, Anamitra Roy ; Natarajan, Sivaramakrishnan R. ; Roy, Sambuddha

Knapsack Cover Subject to a Matroid Constraint

pdf-format:
20.pdf (0.4 MB)

Abstract

We consider the Knapsack Covering problem subject to a matroid constraint. In this problem, we are given an universe U of n items where item i has attributes: a cost c(i) and a size s(i). We also have a demand D. We are also given a matroid M = (U, I) on the set U. A feasible solution S to the problem is one such that (i) the cumulative size of the items chosen is at least D, and (ii) the set S is independent in the matroid M (i.e. S is in I). The objective is to minimize the total cost of the items selected, sum_{i in S}c(i).
Our main result proves a 2-factor approximation for this problem.

The problem described above falls in the realm of mixed packing covering problems. We also consider packing extensions of certain other covering problems and prove that in such cases it is not possible to derive any constant factor pproximations.

BibTeX - Entry

@InProceedings{chakaravarthy_et_al:LIPIcs:2013:4379,
  author =	{Venkatesan T. Chakaravarthy and Anamitra Roy Choudhury and Sivaramakrishnan R. Natarajan and Sambuddha Roy},
  title =	{{Knapsack Cover Subject to a Matroid Constraint}},
  booktitle =	{IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013)},
  pages =	{275--286},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-64-4},
  ISSN =	{1868-8969},
  year =	{2013},
  volume =	{24},
  editor =	{Anil Seth and Nisheeth K. Vishnoi},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2013/4379},
  URN =		{urn:nbn:de:0030-drops-43795},
  doi =		{10.4230/LIPIcs.FSTTCS.2013.275},
  annote =	{Keywords: Approximation Algorithms, LP rounding, Matroid Constraints, Knapsack problems}
}

Keywords: Approximation Algorithms, LP rounding, Matroid Constraints, Knapsack problems
Collection: IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013)
Issue Date: 2013
Date of publication: 10.12.2013

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI