{"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","summary":"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…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-11-07","reactions":{}}