Tight Approximation Algorithms for Maximum Separable Assignment Problems
Tight Approximation Algorithms for Maximum Separable Assignment Problems
复制标题
最大可分离分配问题的紧逼近算法
DOI：
--
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
M. Sviridenko
中科院分区：
文献类型：
--
作者：
L. Fleischer;M. Goemans;V. Mirrokni;M. Sviridenko
可分离分配问题（SAP）由以下各项定义：一组箱子和要在每个箱子中打包的一组物品;用于将物品j分配给箱子i的值fij;以及用于每个箱子的单独打包约束一一即，对于箱子i，适合于箱子i的物品子集的族Ii。我们的目标是把物品打包到箱子里，以最大限度地提高总价值。这类问题包括本文中描述的最大广义分配问题（GAP）1）和分布式缓存问题（DCP）。给出一个求单箱最高值填充的β-近似算法，给出1。一种基于多项式时间LP舍入的（（1 − 1 e）β）近似算法。2.一个简单的多项式时间局部搜索（β β+1 −）近似算法，对于任何> 0。因此，对于SAP的所有允许单箱问题的近似方案的例子，我们得到了具有（1− 1 e −）近似的基于LP的算法和具有（12 −）近似保证的局部搜索算法。此外，对于子问题允许完全多项式近似方案的情况（例如GAP），可以加强基于LP的算法分析，以保证1 − 1 e。以前已知的最好的GAP近似算法是Shmoys和Tardos以及Chekuri和卡纳的12近似。我们的LP算法是基于四舍五入一个新的线性规划松弛，具有可证明的更好的完整性差距。为了补充这些结果，我们证明了SAP和DCP不能在优于1− 1 e的因子内近似，除非NP ≠ DTIME（n log），即使单箱问题存在多项式时间精确算法。IBM T.沃森研究中心。电子邮件：{lkf，sviri}@watson.ibm.com麻省理工学院数学系。电子邮件：goemans@math.mit.edu，mirrokni@theory.csail.mit.edu。部分由NSF赠款CCR 0098018和ITR-0121495以及ONR资助N 00014 -05-1-0148支持。1GAP如下：给定一组箱子和一组对于每个箱子具有不同大小和值的物品，将物品的最大值子集装入箱子中。我们将（1 − 1 e）-近似算法推广到不可分的分配问题，并将其应用于最大化收益约束的组合拍卖和AdWords分配问题。我们推广了局部搜索算法，以产生一个12-近似算法的k-中位数问题的硬容量。最后，我们研究了这些问题的自然定义的博弈论版本，并表明它们的无政府状态的价格为2。我们还证明了最佳反应的移动周期的存在，和指数长的最佳反应路径（纯或汇）均衡。
A separable assignment problem (SAP) is defined by a set of bins and a set of items to pack in each bin; a value, fij , for assigning item j to bin i; and a separate packing constraint for each bin – i.e. for bin i, a family Ii of subsets of items that fit in bin i. The goal is to pack items into bins to maximize the aggregate value. This class of problems includes the maximum generalized assignment problem (GAP)1) and a distributed caching problem (DCP) described in this paper. Given a β-approximation algorithm for finding the highest value packing of a single bin, we give 1. A polynomial-time LP-rounding based ((1 − 1 e )β)approximation algorithm. 2. A simple polynomial-time local search ( β β+1 − )approximation algorithm, for any > 0. Therefore, for all examples of SAP that admit an approximation scheme for the single-bin problem, we obtain an LPbased algorithm with (1− 1 e − )-approximation and a local search algorithm with ( 12 − )-approximation guarantee. Furthermore, for cases in which the subproblem admits a fully polynomial approximation scheme (such as for GAP), the LP-based algorithm analysis can be strengthened to give a guarantee of 1 − 1 e . The best previously known approximation algorithm for GAP is a 12 -approximation by Shmoys and Tardos; and Chekuri and Khanna. Our LP algorithm is based on rounding a new linear programming relaxation, with a provably better integrality gap. To complement these results, we show that SAP and DCP cannot be approximated within a factor better than 1− 1 e unless NP⊆ DTIME(n log ), even if there exists a polynomial-time exact algorithm for the single-bin problem. IBM T. J. Watson Research Center. Email: {lkf,sviri}@watson.ibm.com MIT Department of Mathematics. Email: goemans@math.mit.edu, mirrokni@theory.csail.mit.edu. Supported in part by NSF grants CCR0098018 and ITR-0121495, and ONR grant N00014-05-1-0148. 1GAP is as follows: given a set of bins and a set of items that have a different size and value for each bin, pack a maximum-valued subset of items into the bins. We extend the (1 − 1 e )-approximation algorithm to a nonseparable assignment problem with applications in maximizing revenue for budget-constrained combinatorial auctions and the AdWords assignment problem. We generalize the local search algorithm to yield a 12 − approximation algorithm for the k-median problem with hard capacities. Finally, we study naturally defined game-theoretic versions of these problems, and show that they have price of anarchy of 2. We also prove the existence of cycles of best response moves, and exponentially long best-response paths to (pure or sink) equilibria.