A constant approximation for general max-min fair allocation
An instance consists of $m$ agents, $n$ indivisible items and nonnegative rational values $v_{ij}$, the value of item $j$ to agent $i$. An allocation is a partition $A = (A_1, \dots, A_m)$ of the items among the agents; let $$V(A) = \min_{1 \le i \le m} \sum_{j \in A_i} v_{ij}, \qquad V^* = \max_A V(A).$$ This is max-min fair allocation, which Bansal and Sviridenko called the Santa Claus problem. Bezáková and Dani showed that no polynomial-time algorithm achieves a factor better than $2$ unless $\mathrm{P} = \mathrm{NP}$. Chakrabarty, Chuzhoy and Khanna gave, for every constant $\varepsilon > 0$, a polynomial-time $O(n^{\varepsilon})$-approximation, and a polylogarithmic approximation in quasi-polynomial time. In the restricted case, where $v_{ij} \in \{0, v_j\}$ for every $i$ and $j$, polynomial-time constant-factor approximations are known (see Bamas, Lindermayr, Megow, Rohwedder and Schlöter). Bamas, Lindermayr, Megow, Rohwedder and Schlöter proved that if, for some $\alpha \ge 2$, makespan minimisation on unrelated parallel machines has a polynomial-time $(2 - 1/\alpha)$-approximation, then this problem has a polynomial-time $(\alpha + \varepsilon)$-approximation for every $\varepsilon > 0$.
Problem. Do there exist an absolute constant $C < \infty$ and a polynomial-time algorithm that, on every instance, outputs an allocation $A$ with $V(A) \ge V^*/C$? Running time is measured in the binary encoding length of the instance, and a randomized algorithm that succeeds with probability at least $2/3$ is allowed. The values $v_{ij}$ are arbitrary, not restricted to the form $v_{ij} \in \{0, v_j\}$.
Source: Max-min fair allocation, called the Santa Claus problem by Bansal and Sviridenko (2006); a constant-factor approximation is asked for by Bamas, Lindermayr, Megow, Rohwedder and Schlöter (2024), Introduction, and by Nguyen and Rothe (2026), §5.1.3, Open problem 5. Stated in this form by AIM — Open Applied Problems.
Imported from github.com/MColbrook/AIM.
Classification
- Primary
- OC — Optimization and Control
- Secondary
- CO
- Keywords
- AIM Open Applied Problems, approximation algorithms, max-min fair allocation
References
@inproceedings{bansal2006,
author = {Bansal, Nikhil and Sviridenko, Maxim},
title = {The {S}anta {C}laus problem},
booktitle = {Proceedings of the Thirty-Eighth Annual ACM Symposium on Theory of Computing (STOC '06)},
publisher = {ACM},
year = {2006},
pages = {31--40},
doi = {10.1145/1132516.1132522},
}
@inproceedings{bamas2024,
author = {Bamas, {\'E}tienne and Lindermayr, Alexander and Megow, Nicole and Rohwedder, Lars and Schl{\"o}ter, Jens},
title = {Santa {C}laus meets makespan and matroids: algorithms and reductions},
booktitle = {Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)},
publisher = {SIAM},
year = {2024},
pages = {2829--2860},
doi = {10.1137/1.9781611977912.100},
eprint = {2307.08453},
archivePrefix = {arXiv},
}
@article{nguyen2026,
author = {Nguyen, Trung Thanh and Rothe, J{\"o}rg},
title = {Mathematical programming approaches for social welfare maximization},
journal = {4OR},
volume = {24},
number = {3},
year = {2026},
pages = {259--312},
doi = {10.1007/s10288-026-00628-z},
}
@article{bezakova2005,
author = {Bez{\'a}kov{\'a}, Ivona and Dani, Varsha},
title = {Allocating indivisible goods},
journal = {ACM SIGecom Exchanges},
volume = {5},
number = {3},
year = {2005},
pages = {11--18},
doi = {10.1145/1120680.1120683},
}
@inproceedings{chakrabarty2009,
author = {Chakrabarty, Deeparnab and Chuzhoy, Julia and Khanna, Sanjeev},
title = {On allocating goods to maximize fairness},
booktitle = {2009 50th Annual IEEE Symposium on Foundations of Computer Science (FOCS)},
publisher = {IEEE},
year = {2009},
pages = {107--116},
doi = {10.1109/FOCS.2009.51},
eprint = {0901.0205},
archivePrefix = {arXiv},
}
@misc{aim-general-santa-claus,
author = {Brunton, Steve and Colbrook, Matthew J. and de Hoop, Maarten V. and Stepaniants, George and Townsend, Alex and Ward, Rachel},
title = {{A constant approximation for general max-min fair allocation}},
howpublished = {AIM --- Open Applied Problems, GitHub repository},
year = {2026},
url = {https://github.com/MColbrook/AIM/blob/a153f469ee0ea64e876b2ad97c79d252c19a3e22/problems/279-general-santa-claus.md},
note = {Entry 279 at commit a153f46, 2026-10-13},
}
Citing this problem
This identifier is permanent. It will not change if the problem is solved, reclassified or withdrawn.
OP-00437, "A constant approximation for general max-min fair allocation", clopen.solutions.