Beyond Worst-Case Analysis (Lecture 15: Smoothed Complexity and Pseudopolynomial-Time Algorithms)

Описание: For binary optimization problems, polynomial smoothed complexity implies and is implied by (Las Vegas randomized) pseudopolynomial worst-case complexity.
Full course playlist:    • Beyond Worst-Case Analysis (Stanford CS264...  
Book: https://www.amazon.com/dp/1108494315
Lecture notes: http://timroughgarden.org/w17/l/l18.pdf