Online Makespan Minimization: Beat LPT by Dynamic Locking
Published in WINE 2025, 2025
Authors: Zhaozi Wang, Zhiwei Ying, and Yuhao Zhang
Venue: 21st Conference on Web and Internet Economics (WINE 2025)
| Links: arXiv | DOI |
We study online makespan minimization when jobs arrive over time. The dynamic-locking technique achieves a competitive ratio strictly below 1.5 for every fixed number of identical machines, improving on the classical LPT guarantee.