Beyond Worst-Case Analysis (Lecture 15: Smoothed Complexity and Pseudopolynomial-Time Algorithms)
Tim Roughgarden Lectures · 82:34
For binary optimization problems of the form “pick a feasible 0-1 vector that maximizes \(v^\top x\)”, an algorithm with polynomial *smooth* complexity exists if and only if the problem has (randomized) *pseudopolynom...