MaxMin allocation via degree lower-bounded arborescences

ABSTRACT

We consider the problem of MaxMin allocation of indivisible goods. There are m items to be distributed among n players. Each player $i$ has a nonnegative valuation p_ij for an item j, and the goal is to allocate items to players so as to maximize the minimum total valuation received by each player. There is a large gap in our understanding of this problem. The best known positive result is an ~O(√ n)-approximation algorithm, while there is only a factor 2 hardness known. Better algorithms are known for the restricted assignment case where each item has exactly one nonzero value for the players. We study the effect of bounded degree for items: each item has a nonzero value for at most D players. We show that essentially the case D = 3 is equivalent to the general case, and give a 4-approximation algorithm for D = 2.

The current algorithmic results for MaxMin Allocation are based on a complicated LP relaxation called the configuration LP. We present a much simpler LP which is equivalent in power to the configuration LP. We focus on a special case of MaxMin Allocation-a family of instances on which this LP has a polynomially large gap. The technical core of our result for this case comes from an algorithm for an interesting new optimization problem on directed graphs, MaxMinDegree Arborescence, where the goal is to produce an arborescence of large outdegree. We develop an n^ε-approximation for this problem that runs in n^O(1/ε) time and obtain a a polylogarithmic approximation that runs in quasipolynomial time, using a lift-and-project inspired LP formulation. In fact, we show that our results imply a rounding algorithm for the relaxations obtained by t rounds of the Sherali-Adams hierarchy applied to a natural LP relaxation of the problem. Roughly speaking, the integrality gap of the relaxation obtained from t rounds of Sherali-Adams is at most n^1/t. We are able to extend the latter result to a more general class of instances. Along the way, we prove a result about the existence of a perfect matching in a probabilistically pruned graph which may be of independent interest.

REFERENCES

• 1: N. Alon, Y. Azar, G. J. Woeginger, and T. Yadid. Approximation schemes for scheduling on parallel machines. Journal of Scheduling, 1(1):55--66, 1998.
• 2: Arash Asadpour , Uriel Feige , Amin Saberi, Santa Claus Meets Hypergraph Matchings, Proceedings of the 11th international workshop, APPROX 2008, and 12th international workshop, RANDOM 2008 on Approximation, Randomization and Combinatorial Optimization: Algorithms and Techniques, August 25-27, 2008, Boston, MA, USA [doi>10.1007/978-3-540-85363-3_2]
• 3: Arash Asadpour , Amin Saberi, An approximation algorithm for max-min fair allocation of indivisible goods, Proceedings of the thirty-ninth annual ACM symposium on Theory of computing, June 11-13, 2007, San Diego, California, USA [doi>10.1145/1250790.1250808]
• 4: Nikhil Bansal , Maxim Sviridenko, The Santa Claus problem, Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, May 21-23, 2006, Seattle, WA, USA [doi>10.1145/1132516.1132522]
• 5: M. Bateni, M. Charikar, and V. Guruswami. New approximation algorithms for degree lower-bounded arborescences and max-min allocation. Technical Report TR-848-09, Computer Science Department, Princeton University, March 2009.
• 6: Ivona Bezáková , Varsha Dani, Allocating indivisible goods, ACM SIGecom Exchanges, v.5 n.3, p.11-18, April 2005 [doi>10.1145/1120680.1120683]
• 7: D. Chakrabarty, J. Chuzhoy, and S. Khanna. On allocating goods to maximize fairness. CoRR, abs/0901.0205, 2009.
• 8: Tomáš Ebenlendr , Marek Křćal , Jiří Sgall, Graph balancing: a special case of scheduling unrelated parallel machines, Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms, p.483-490, January 20-22, 2008, San Francisco, California
• 9: Uriel Feige, On allocations that maximize fairness, Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms, p.287-293, January 20-22, 2008, San Francisco, California
• 10: D. Golovin. Max-min fair allocation of indivisible goods. Technical Report CMU-CS-05-144, School of Computer Science, Carnegie Mellon University, June 2005.
• 11: Subhash Khot , Ashok Kumar Ponnuswami, Approximation Algorithms for the Max-Min Allocation Problem, Proceedings of the 10th International Workshop on Approximation and the 11th International Workshop on Randomization, and Combinatorial Optimization. Algorithms and Techniques, August 20-22, 2007, Princeton, NJ, USA [doi>10.1007/978-3-540-74208-1_15]
• 12: J. K. Lenstra , D. B. Shmoys , É. Tardos, Approximation algorithms for scheduling unrelated parallel machines, Mathematical Programming: Series A and B, v.46 n.3, p.259-271, February 1990 [doi>10.1007/BF01585745]
• 13: G. J. Woeginger. A polynomial-time approximation scheme for maximizing the minimum machine completion time. Operations Research Letters, 20(4):149--154, 1997.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Computations on discrete structures

General Terms:
Algorithms, Economics, Theory

Keywords:
approximation algorithms, graphs, lift-and-project, linear programming