Tight Approximation Algorithms for Maximum Separable Assignment Problems

• 成果类型: Article
• 署名作者: Fleischer, Lisa; Goemans, Michel X.; Mirrokni, Vahab S.; Sviridenko, Maxim
• 署名单位: Dartmouth College; Massachusetts Institute of Technology (MIT); Alphabet Inc.; Google Incorporated; International Business Machines (IBM); IBM USA
• 刊物名称: MATHEMATICS OF OPERATIONS RESEARCH
• ISSN/ISSBN: 0364-765X
• DOI: 10.1287/moor.1110.0499
• 发表日期: 2011
• 页码: 416-431

摘要

A separable assignment problem (S A P) is defined by a set of bins and a set of items to pack in each bin; a value, f(ij), for assigning item j to bin i; and a separate packing constraint for each bin-i.e., for each bin, a family of subsets of items that fit in to that bin. The goal is to pack items into bins to maximize the aggregate value. This class of problems includes the maximum generalized assignment problem (G A P)(1) and a distributed caching problem (DCP) described in this paper. Given a beta-approximation algorithm for finding the highest value packing of a single bin, we give (i) A polynomial-time LP-rounding based ((1 - 1/e)beta)-approximation algorithm. (ii) A simple polynomial-time local search (beta/(beta + 1) - epsilon)-approximation algorithm, for any epsilon > 0. Therefore, for all examples of S A P that admit an approximation scheme for the single-bin problem, we obtain an LP-based algorithm with (1 - 1/e - epsilon)-approximation and a local search algorithm with (1/2 - epsilon)-approximation guarantee. Furthermore, for cases in which the subproblem admits a fully polynomial approximation scheme (such as for G A P), the LP-based algorithm analysis can be strengthened to give a guarantee of 1 - 1/e. The best previously known approximation algorithm for G A P is a 1/2-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 S A P and D C P cannot be approximated within a factor better than 1 - 1/e unless NP subset of DTIME(n(O(log log n))), even if there exists a polynomial-time exact algorithm for the single-bin problem. We extend the (1 - 1/e)-approximation algorithm to a constant-factor approximation algorithms for 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 1/2 - epsilon. approximation algorithm for the maximum k-median problem with hard capacities.