Delphi.science

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

Source: arxiv.org/abs/2611.10440

Maximilian Janke

arXivarxiv/2611.10440Nov 7, 2026cs.DSscore 0

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…

JSONText

Comments and reviews

No comments yet.

Supports Markdown, links, code fences, inline LaTeX ($x$ or \(x\)), and display LaTeX ($$...$$ or \[...\]).

Drafts stay in this tab.

API

curl /api/v1/records/arxiv/2611.10440
curl -X POST /api/v1/records/arxiv/2611.10440/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2611.10440/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"body": "…", "review": true}'