Tight approximation algorithms for maximum general assignment problems

By Lisa Fleischer, Michel X. Goemans, Vahab S. Mirrokni, Maxim Sviridenko. ACM-SIAM Symposium on Discrete Algorithms, 2006

307 citations recorded by the source corpus.

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 Li 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 give1. 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 LP-based algorithm with (1 - 1/e - ε)-approximation and a local search algorithm with (1/2-ε)-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 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 SAP and DCP cannot be approximated within a factor better than 1 -1/e unless NP⊆ DTIME(nO(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 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-ε 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.

Subfields: Computational Theory and Mathematics, Computer Networks and Communications

View Paper: https://www.semanticscholar.org/paper/68feb145c4eb4421c7f334d0a992d7c2095b91e6

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Theory and Mathematics

In Computer Networks and Communications

Citations in the corpus

Online Submodular Maximization with Preemption (2015, background): “Sub-modular maximization captures well known combinatorial optimization problems such as: Max-Cut [32, 36, 39, 40, 53], Max-DiCut [20, 32, 34], Generalized Assignment [11, 12, 24, 29], and Max-Facility-Location [2, 14, 15].”
Online Matching and Ad Allocation (2013, unknown): “[47], and by Feige and Vondrak [43] to 1 − (1)e + ε for a very small constant ε < 10−5.”
Maximizing a Submodular Set Function Subject to a Matroid Constraint (Extended Abstract) (2007, methodology): “We note that the approximation ratio for GAP has been improved to 1−1/e+δ1 for a small δ1 > 0 in [8] using the same LP as in [10].”
Maximizing a Monotone Submodular Function Subject to a Matroid Constraint (2011, methodology): “A simple matroid constraint that is of much importance in applications [9, 36, 7, 8, 19] is the partition matroid: X is partitioned into ` sets X1, X2, .”
Online budgeted matching in random input models with applications to Adwords (2008, background): “We define this class formally in Section 3, but mention here that this class also contains the problems of bipartite matching (all bids 0 or 1, all budgets 1) and b-matching, for any positive integer b (all bids 0 or 1, all budgets b). The offlineversion of this problem is NP-hard, with the best kno”
Optimal approximation for the submodular welfare problem in the value oracle model (2008, methodology): “previously known factors of α(1 − 1/e) [11] and α/(1 + α) [2, 12] in this framework.”