# Solving Max-Min Fair Resource Allocations Quickly on Large Graphs

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 15 Oct 2023.

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

- [Robust Heuristic Algorithm Design with LLMs](https://mlsanity.com/paper/2510.08755/) (2025)
- [m4: A Learned Flow-level Network Simulator](https://mlsanity.com/paper/2503.01770/) (2025)
- [From Simulation to Deep Learning: Survey on Network Performance Modeling Approaches](https://mlsanity.com/paper/2603.28394/) (2026)

## Abstract (arXiv)

We consider the max-min fair resource allocation problem. The best-known solutions use either a sequence of optimizations or waterfilling, which only applies to a narrow set of cases. These solutions have become a practical bottleneck in WAN traffic engineering and cluster scheduling, especially at larger problem sizes. We improve both approaches: (1) we show how to convert the optimization sequence into a single fast optimization, and (2) we generalize waterfilling to the multi-path case. We empirically show our new algorithms Pareto-dominate prior techniques: they produce faster, fairer, and more efficient allocations. Some of our allocators also have theoretical guarantees: they trade off a bounded amount of unfairness for faster allocation. We have deployed our allocators in Azure's WAN traffic engineering pipeline, where we preserve solution quality and achieve a roughly 3× speedup.