pipette
ESEspañol

Lower Bounds Above for Online Makespan Minimization on Four Identical Machines

Maximilian Janke

Preprint

In the authors' words

For deterministic online makespan minimization, identical machines is the smallest case whose optimal competitive ratio is open: it is known only to lie between and . We prove a lower bound of using a single branching layer, and refine the construction with a second, mirrored branching layer to obtain , closing about a third of the gap. Our constructions are the first branching adversaries for machines, and the first explicit lower bounds for online makespan minimization in which the adversary presents jobs in non-monotone order of size.

Main resultLimitation the authors admit

Appeared: Tuesday, November 10. arXiv. Preprint, not yet peer-reviewed.