Approximation hardness and online algorithms for resource scheduling
summary
Proves concrete hardness: a gap-preserving reduction shows no (3/2 − ε)-approximation for makespan under integer resource demands unless P=NP, and the natural LP has an integrality gap proportional to the resource budget. Gives online algorithms with an O(log k) competitive ratio and a matching Ω(log k) lower bound via adversarial DAGs. Techniques combine LP relaxations, randomized primal-dual rounding, and potential-function analysis; simulations on synthetic DAGs confirm schedules meet the theoretical bounds within constant factors.
AI-written summary · about
chapters (8)
- 0:00Resource scheduling problem
- 1:27Scheduling model and constraints
- 2:11Resource budget and usage
- 3:00Approximation hardness results
- 12:45Online algorithms for scheduling
- 25:30Experimental validation
- 30:15Open problems and future work
- 34:00Q&A
related talks
59mHardness for Graph Problems - Reductions Based on APSP and SETH
19mLook Before, Before You Leap: Online Vector Load Balancing with Few Reassignments
52mFlow Time Scheduling with Uncertain Processing Time
23mTowards General and Tight Hardness Results for Graph Problems
35mSuperlinear Lower Bounds for Multipass Graph Processing
19mDeterministic Dynamic Matching In Worst-Case Update Time
17mSolving Max-Min Fair Resource Allocations Quickly on Large Graphs
30mOptimal Lower Bounds for Distributed and Streaming Spanning Forest Computation