Lower Bounds Above $\sqrt{3}$ for Online Makespan Minimization on Four Identical Machines
Source: arxiv.org/abs/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…
Comments and reviews
No comments yet.
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}'