Processing math: 100%
Skip to yearly menu bar Skip to main content


Poster

Minimalistic Predictions for Online Class Constraint Scheduling

Dorian Guyot · Alexandra Lassota

Hall 3 + Hall 2B #332
[ ]
Sat 26 Apr midnight PDT — 2:30 a.m. PDT

Abstract: We consider online scheduling with class constraints. That is, we are given m machines, each with k class slots. Upon receiving a job j with class cj, an algorithm needs to allocate j on some machine i. The goal is to minimize the makespan while not assigning more than k different classes onto each machine.While the offline case is well understood and even (E)PTAS results are known [Jansen, Lassota, Maack SPAA'20, Chen Jansen Luo Zhang COCOA'16], the online case admits strong impossibility results in classical competitive analysis [Epstein, Lassota, Levin, Maack, Rohwedder STACS'22].We overcome these daunting results by investigating the problem in a learning-augmented setting where an algorithm can access possibly erroneous predictions. We present new algorithms with competitive ratios independent of m and tight lower bounds for several classical and problem-specific prediction models. We thereby give a structured overview of what additional information helps in the design of better scheduling algorithms.

Live content is unavailable. Log in and register to view live content