Online Makespan Scheduling under Scenarios

Ekin Ergen · 2025

Read Online Makespan Scheduling under Scenarios by Ekin Ergen (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2507-04016.txt.

Description

Ekin Ergen studies online scheduling where jobs must be placed under future scenario limits, in work from twenty twenty-five. Classic scheduling spreads jobs across like machines to cut the longest load. The twist here is scenarios, which are named subsets of jobs. The goal is to cap the worst load inside any one scenario. Jobs arrive online, so choices must be made with no full view ahead.

Ergen maps how well online methods can compete across machine and scenario counts. Tight and near-tight bounds are proved for those settings. Fresh constructions supply many of the hard cases and the matching methods. A special case with unit job lengths links tightly to graph colouring. Colouring tricks steer hard cases that prove online methods cannot do better. Those hard cases in turn give new lower bounds for online colouring. The two fields thus sharpen each other.

Catalog record

CREATOREkin Ergen
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE117 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2507-04016

Browse the full library · About the Tower of Babel