Ab 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，T) 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 ? T). The objective is to minimize the total cost of the items selected, ∑_(i∈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 approximations.
展开▼
机译：AB我们将背包覆盖问题受到Matroid'Constraint的问题。在这个问题中，我们给了一个项目的Universe U的项目我具有属性的项目：成本c（i）和尺寸s（i）。我们也有一个需求D.我们还给出了集合U中的Matroid M =（U，T）。一个可行的解决方案S到问题的情况是（i）所选择的物品的累积大小至少为d （II）SET S在MATROID M中独立于MATROID M.（即S-T）。目的是最大限度地减少所选项目的总成本，Σ_（i∈s）c（i）我们的主要结果证明了这个问题的2因素近似值。上面描述的问题属于混合包装覆盖问题的领域。我们还考虑某些其他覆盖问题的包装扩展，并证明在这种情况下，不可能得出任何恒定因子近似。
展开▼
