论文标题
supsodular多背包问题的简单确定性近似
Simple Deterministic Approximation for Submodular Multiple Knapsack Problem
论文作者
论文摘要
在过去的几十年中，suppodular最大化一直是理论计算机科学和组合优化的核心主题。在各种限制因素上，已经为问题设计了大量良好的近似算法。在本文中，我们考虑了次管多背包问题（SMKP）。在SMKP中，每个元素子集的利润由单调下一个功能指定。目的是在多个垃圾箱（背包）上找到可行的元素包装，以最大程度地提高利润。最近，Fairstein等人〜[ESA20]提出了一个几乎最佳的$（1-e^{ - 1}-ε）$ - SMKP的近似算法。它们的算法是通过组合配置LP（用于垃圾箱填料的分组技术）以及用于亚键最大化的连续贪婪算法获得的。结果，该算法有些复杂，并且本质上是随机的。在本文中，我们提出了SMKP的一种简单的确定性组合算法，该算法达到了$（1-e^{ - 1}-ε）$ - 近似值。与Fairstein等人相比，我们的算法基于截然不同的想法。
Submodular maximization has been a central topic in theoretical computer science and combinatorial optimization over the last decades. Plenty of well-performed approximation algorithms have been designed for the problem over a variety of constraints. In this paper, we consider the submodular multiple knapsack problem (SMKP). In SMKP, the profits of each subset of elements are specified by a monotone submodular function. The goal is to find a feasible packing of elements over multiple bins (knapsacks) to maximize the profit. Recently, Fairstein et al.~[ESA20] proposed a nearly optimal $(1-e^{-1}-ε)$-approximation algorithm for SMKP. Their algorithm is obtained by combining configuration LP, a grouping technique for bin packing, and the continuous greedy algorithm for submodular maximization. As a result, the algorithm is somewhat sophisticated and inherently randomized. In this paper, we present an arguably simple deterministic combinatorial algorithm for SMKP, which achieves a $(1-e^{-1}-ε)$-approximation ratio. Our algorithm is based on very different ideas compared with Fairstein et al.~[ESA20].
