Id: arxiv/2611.10440 Url: https://arxiv.org/abs/2611.10440 Tags: cs.DS, math.OC Score: 0 Title: Lower Bounds Above $\sqrt{3}$ for Online Makespan Minimization on Four Identical Machines Domain: cs.DS Source: arxiv Authors: Maximilian Janke Reviews: 0 Subject: cs.DS Category: research Comments: 0 Disputed: false Division: cs Mentions: 0 Discussed: 0 Published: 2026-11-07 Page: https://delphi.science/r/arxiv/2611.10440 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…