Algorithms for NP-Hard Problems (Section 20.1: Makespan Minimization) [Part 2 of 2]
Tim Roughgarden Lectures · 21:38
Graham’s list-scheduling heuristic for the NP-hard minimum-makespan problem is proven to produce a schedule whose makespan \(M\) is at most \((2 - 1/m)\) times the optimum \(M^*\), by relating both quantities to the l...