A (1+epsilon)-approximation for Makespan Scheduling with Precedence Constraints Using LP Hierarchies
summary
Claim: a 1+ε approximation for makespan on unit-length jobs with constant M, achieved by strengthening the time-indexed LP via the Sherali–Adams hierarchy until the integrality gap falls to 1+ε. Algorithm uses a binary interval decomposition, repeated conditioning to collapse long chains, throws away a tiny middle layer, and recursively schedules remaining subinstances, finishing with EDF/matching to place top-level jobs. Needs quasi-polynomial rounds (hence quasi-polynomial time) and succeeds for constant M.
AI-written summary · about