论文标题
模块化和下二极管优化，并通过分数分组进行多个背包约束
Modular and Submodular Optimization with Multiple Knapsack Constraints via Fractional Grouping
论文作者
论文摘要
对一组项目的多个背包约束由一组任意能力的垃圾箱定义，每个项目的权重。约束的分配是将项目子集的分配给垃圾箱，并遵守垃圾箱的容量。在本文中，我们提出了一种统一的算法，该算法可为涉及多个背包约束的一系列宽类和模块化优化问题产生有效的近似值。一个值得注意的例子是用于多项选择多重背包的多项式时间近似方案，以$ 2 $的最佳比例提高。另一个示例是非单调的多重背包，为此，我们获得了$（0.385- \ varepsilon）$ - 近似值，与单个knapsack约束相匹配。我们的算法的鲁棒性是通过应用经典线性分组技术的新型分数变体来实现的，该技术具有独立的兴趣。
A multiple knapsack constraint over a set of items is defined by a set of bins of arbitrary capacities, and a weight for each of the items. An assignment for the constraint is an allocation of subsets of items to the bins which adheres to bin capacities. In this paper we present a unified algorithm that yields efficient approximations for a wide class of submodular and modular optimization problems involving multiple knapsack constraints. One notable example is a polynomial time approximation scheme for Multiple-Choice Multiple Knapsack, improving upon the best known ratio of $2$. Another example is Non-monotone Submodular Multiple Knapsack, for which we obtain a $(0.385-\varepsilon)$-approximation, matching the best known ratio for a single knapsack constraint. The robustness of our algorithm is achieved by applying a novel fractional variant of the classical linear grouping technique, which is of independent interest.
