# Restricted Max-Min Fair Allocation

arXiv: https://arxiv.org/abs/1804.10902 · HTML: https://mlsanity.com/paper/1804.10902/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 29 Apr 2018.

## Built on by (most cited first, 1 of 1)

- [Settling the Computational Complexity of Max-Min Allocation with Ternary Valuations](https://mlsanity.com/paper/2610.05237/) (2026)

## Abstract (arXiv)

The restricted max-min fair allocation problem seeks an allocation of resources to players that maximizes the minimum total value obtained by any player. It is NP-hard to approximate the problem to a ratio less than 2. Comparing the current best algorithm for estimating the optimal value with the current best for constructing an allocation, there is quite a gap between the ratios that can be achieved in polynomial time: roughly 4 for estimation and roughly 6 + 2√10 for construction. We propose an algorithm that constructs an allocation with value within a factor of 6 + δ from the optimum for any constant δ > 0. The running time is polynomial in the input size for any constant δ chosen.