论文标题
一种几乎最佳的单调下一个多背心的近似算法
An Almost Optimal Approximation Algorithm for Monotone Submodular Multiple Knapsack
论文作者
论文摘要
我们研究了受到多个背包约束的最大化单调下调功能的问题。输入是一组$ i $的物品，每个物品具有非负重量，以及一组任意能力。此外，我们还为我们的子集提供了一个子模块，单调和非负功能$ f $。目的是找到垃圾箱中$ a \ subseteq i $的子集的包装，以使$ f（a）$最大化。 我们的主要结果是几乎最佳的多项式时间$（1-e^{ - 1} - \ varepsilon）$ - 对于任何$ \ varepsilon> 0 $ $ \ varepsilon> 0 $。该算法依赖于一种结构化技术，该技术将一般多重背包约束转换为约束，其中将垃圾箱分配为指数增加的基础性，每个基数由均匀能力的垃圾箱组成。我们通过结合结构与对knapsack限制的基础优化技术的精制分析相结合来得出结果。
We study the problem of maximizing a monotone submodular function subject to a Multiple Knapsack constraint. The input is a set $I$ of items, each has a non-negative weight, and a set of bins of arbitrary capacities. Also, we are given a submodular, monotone and non-negative function $f$ over subsets of the items. The objective is to find a packing of a subset of items $A \subseteq I$ in the bins such that $f(A)$ is maximized. Our main result is an almost optimal polynomial time $(1-e^{-1}-\varepsilon)$-approximation algorithm for the problem, for any $\varepsilon>0$. The algorithm relies on a structuring technique which converts a general multiple knapsack constraint to a constraint in which the bins are partitioned into groups of exponentially increasing cardinalities, each consisting of bins of uniform capacity. We derive the result by combining structuring with a refined analysis of techniques for submodular optimization subject to knapsack constraints.
