Scheduling on Related Machines

on YouTube ↗29m

" summary

Claims a constant competitive algorithm for online scheduling on related machines for arbitrary l_q norms, using a new fractional relaxation with two terms (a convex q-powered load term plus a linear per-job term) solved by assigning infinitesimal pieces to the machine minimizing the max derivative. Rounding groups machines so total speeds double, then uses group-and-median rounding plus identical-machine packing inside groups. Analysis avoids multiplicative weights and extends to multi-resource (multi-dimensional) loads, losing only constant factors.

AI-written summary · about

" chapters (8)

1. 0:00Intro
2. 1:40Scheduling Objectives
3. 5:48Load Balancing on Related Machines
4. 9:30A Continuous Relaxation
5. 16:02Fractional Algorithm: Analysis
6. 17:02Bounding jobs opt assigns to faster machines
7. 24:05Rounding algorithm: First attempt
8. 26:49Extensions: Vector scheduling for d-dimensional jobs