The Simplex Algorithm is NP-mighty.

Yann Disser, Martin Skutella

Browse the full SODA paper archive.