Improved Approximation for Non-preemptive Scheduling via Time-indexed LP Relaxations

on YouTube ↗30m

" summary

Uses a time-indexed LP with a rectangle view of job start times, then samples a rectangle per job and randomizes an offset (choice of a theta distribution) to round to a non‑preemptive schedule. For unrelated machines with release times this yields a 1.8786-approximation by tightening the idle‑time bound; for identical machines with precedence constraints it improves the old 4× bound to a concrete 2+2/√2-style bound via random ordering and busy/idle decomposition.

AI-written summary · about

" chapters (8)

1. 0:00Intro
2. 0:28Non-Preemptive Scheduling Problems to Minimize Weighted Completion Time
3. 5:51Main Theme: Time-Indexed LP Relaxation
4. 12:41Proof of 2-Approximation
5. 17:16Analyze Effect of Using Non-Uniform Distributions
6. 22:20List Scheduling Algorithm Gives 4-Approximation
7. 25:55Our Algorithm
8. 28:08Open Problems