Lower Bounds Above for Online Makespan Minimization on Four Identical Machines
En palabras de los autores
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.
Resultado principalLimitación que admiten los autores
Apareció: martes, 10 de noviembre. arXiv. Preprint, todavía sin revisión por pares.