Beat factor two for scheduling on unrelated machines
An instance consists of $m$ machines, $n$ jobs and nonnegative rational processing times $p_{ij}$ for running job $j$ on machine $i$. An assignment $f : \{1, \dots, n\} \to \{1, \dots, m\}$ has makespan $C(f) = \max_i \sum_{j : f(j) = i} p_{ij}$. Lenstra, Shmoys and Tardos gave a polynomial-time algorithm that always returns an assignment with makespan at most twice the minimum, and showed that no polynomial-time algorithm guarantees a factor below $3/2$ unless $\mathrm{P} = \mathrm{NP}$. Shchepin and Vakhania improved the factor to $2 - 1/m$. Bamas, Lindermayr, Megow, Rohwedder and Schlöter showed that an affirmative answer to the problem below would give a constant-factor approximation for max-min fair allocation (the Santa Claus problem).
Problem. Is there an absolute constant $\varepsilon > 0$ and an algorithm, running in time polynomial in the binary input length, that always returns an assignment $f$ with $C(f) \le (2 - \varepsilon) \min_g C(g)$? A randomized algorithm succeeding with probability at least $2/3$ also counts.
Source: Lenstra, Shmoys and Tardos (1990), the gap between their factor-2 algorithm and their 3/2 hardness bound; listed among the open problems of Schuurman and Woeginger (1999), as cited by Bamas, Lindermayr, Megow, Rohwedder and Schlöter (2024).
Imported from github.com/MColbrook/AIM.
Classification
- Primary
- OC — Optimization and Control
- Secondary
- CO
- Keywords
- AIM Open Applied Problems, approximation algorithms, scheduling, unrelated parallel machines
References
@article{lenstra1990,
author = {Lenstra, Jan Karel and Shmoys, David B. and Tardos, {\'E}va},
title = {Approximation algorithms for scheduling unrelated parallel machines},
journal = {Math. Programming},
volume = {46},
number = {1-3},
year = {1990},
pages = {259--271},
doi = {10.1007/BF01585745},
}
@article{schuurman1999,
author = {Schuurman, Petra and Woeginger, Gerhard J.},
title = {Polynomial time approximation algorithms for machine scheduling: ten open problems},
journal = {J. Sched.},
volume = {2},
number = {5},
year = {1999},
pages = {203--213},
doi = {10.1002/(SICI)1099-1425(199909/10)2:5<203::AID-JOS26>3.0.CO;2-5},
}
@article{shchepin2005,
author = {Shchepin, Evgeny V. and Vakhania, Nodari},
title = {An optimal rounding gives a better approximation for scheduling unrelated machines},
journal = {Oper. Res. Lett.},
volume = {33},
number = {2},
year = {2005},
pages = {127--133},
doi = {10.1016/j.orl.2004.05.004},
}
@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},
}
@misc{aim-unrelated-machine-makespan,
author = {Brunton, Steve and Colbrook, Matthew J. and de Hoop, Maarten V. and Stepaniants, George and Townsend, Alex and Ward, Rachel},
title = {{Beat factor two for scheduling on unrelated machines}},
howpublished = {AIM --- Open Applied Problems, GitHub repository},
year = {2026},
url = {https://github.com/MColbrook/AIM/blob/a153f469ee0ea64e876b2ad97c79d252c19a3e22/problems/278-unrelated-machine-makespan.md},
note = {Entry 278 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-00488, "Beat factor two for scheduling on unrelated machines", clopen.solutions.