arXiv:2611.10440 · v1

Lower Bounds Above $\sqrt{3}$ for Online Makespan Minimization on Four Identical Machines

首次提交 2026-11-07 11:41

版本更新 2026-11-07 11:41

雷达观测 2026-11-10 10:11

摘要

For deterministic online makespan minimization, $m = 4$ identical machines is the smallest case whose optimal competitive ratio is open: it is known only to lie between $\sqrt{3} \approx 1.73205$ and $26/15 \approx 1.73333$. We prove a lower bound of $14383/8304 \approx 1.73206$ using a single branching layer, and refine the construction with a second, mirrored branching layer to obtain $14350/8283 \approx 1.73246$, closing about a third of the gap. Our constructions are the first branching adversaries for $m = 4$ machines, and the first explicit lower bounds for online makespan minimization in which the adversary presents jobs in non-monotone order of size.