LP Relaxations of Some NP-Hard Problems Are as Hard as Any LP.

Daniel Prusa, Toms Werner

Browse the full SODA paper archive.