Abstract
We consider the problem of max-min fair allocation of indivisible goods. Our focus will be on the restricted version of the problem in which there are m items, each of which associated with a non-negative value. There are also n players and each player is only interested in some of the items. The goal is to distribute the items between the players such that the least happy person is as happy as possible, i.e. one wants to maximize the minimum of the sum of the values of the items given to any player. This problem is also known as the Santa Claus problem [3]. Feige [9] proves that the integrality gap of a certain configuration LP, described by Bansal and Sviridenko [3], is bounded from below by some (unspecified) constant. This gives an efficient way to estimate the optimum value of the problem within a constant factor. However, the proof in [9] is nonconstructive: it uses the Lovasz local lemma and does not provide a polynomial time algorithm for finding an allocation. In this paper, we take a different approach to this problem, based upon local search techniques for finding perfect matchings in certain classes of hypergraphs. As a result, we prove that the integrality gap of the configuration LP is bounded by \(\frac{1}{5}\). Our proof is nonconstructive in the following sense: it does provide a local search algorithm which finds the corresponding allocation, but this algorithm is not known to converge to a local optimum in a polynomial number of steps.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Aharoni, R., Haxell, P.: Hall’s theorem for hypergraphs. Journal of Graph Theory 35, 83–88 (2000)
Asadpour, A., Saberi, A.: An Approximation Algorithm for Max-Min Fair Allocation of Indivisible Goods. In: Proceedings of the ACM Symposium on Theory of Computing (STOC) (2007)
Bansal, N., Sviridenko, M.: The Santa Claus problem. In: Proceedings of the ACM Symposium on Theory of Computing (STOC) (2006)
Bezakova, I., Dani, V.: Allocating indivisible goods. SIGecom Exchanges (2005)
Brams, S.J., Taylor, A.D.: Fair division: from Cake Cutting to Dispute Resolution. Cambridge University Press, Cambridge (1996)
Dobzinski, S., Schapira, M.: An improved approximation algorithm for combinatorial auctions with submodular bidders. In: Proceedings of Symposium on Discrete Algorithms (SODA) (2006)
Ebenlendr, T., Krcal, M., Sgall, J.: Graph Balancing: A Special Case of Scheduling Unrelated Parallel Machines. In: Proceedings of Symposium on Discrete Algorithms (SODA) (2008)
Feige, U.: On maximizing welfare when utility functions are subadditive. In: Proceedings of the ACM Symposium on Theory of Computing (STOC) (2006)
Feige, U.: On allocations that maximize fairness. In: Proceedings of Symposium on Discrete Algorithms (SODA) (2008)
Feige, U., Vondrak, J.: Approximation algorithms for allocation problems: Improving the factor of 1 - 1/e. In: Proceedings of Foundations of Computer Science (FOCS) (2006)
Haxell, P.E.: A Condition for Matchability in Hypergraphs. Graphs and Combinatorics 11, 245–248 (1995)
Johnson, D.S., Papadimitriou, C.H., Yannakakis, M.: How easy is local search? Journal of Computer and System Sciences 37, 79–100 (1988)
Kessler, O.: Matchings in Hypergraphs. D.Sc. Thesis, Technion (1989)
Kuhn, H.W.: The Hungarian Method for the assignment problem. Naval Research Logistic Quarterly 2, 83–97 (1955)
Lenstra, J.K., Shmoys, D.B., Tardos, E.: Approximation algorithms for scheduling unrelated parallel machines. Mathematical Programming, Series A (1993)
Steinhaus, H.: The problem of fair division. Econometrica (1948)
Vondrak, J.: Optimal approximation for the Submodular Welfare Problem in the value oracle model. In: Proceedings of the ACM Symposium on Theory of Computing (STOC) (2008)
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 2008 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Asadpour, A., Feige, U., Saberi, A. (2008). Santa Claus Meets Hypergraph Matchings. In: Goel, A., Jansen, K., Rolim, J.D.P., Rubinfeld, R. (eds) Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques. APPROX RANDOM 2008 2008. Lecture Notes in Computer Science, vol 5171. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-85363-3_2
Download citation
DOI: https://doi.org/10.1007/978-3-540-85363-3_2
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-85362-6
Online ISBN: 978-3-540-85363-3
eBook Packages: Computer ScienceComputer Science (R0)