文章基本信息

标题：Knapsack Cover Subject to a Matroid Constraint
本地全文：下载
作者：Venkatesan T. Chakaravarthy ; Anamitra Roy Choudhury ; Sivaramakrishnan R. Natarajan 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2013
卷号：24
页码：275-286
DOI：10.4230/LIPIcs.FSTTCS.2013.275
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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.
关键词：Approximation Algorithms; LP rounding; Matroid Constraints; Knapsack problems