| Article ID: | iaor20091309 |
| Country: | Netherlands |
| Volume: | 5 |
| Issue: | 2 |
| Start Page Number: | 174 |
| End Page Number: | 185 |
| Publication Date: | May 2008 |
| Journal: | Discrete Optimization |
| Authors: | Karp Richard M. |
| Keywords: | programming: linear, programming: integer, combinatorial optimization |
George Dantzig created the simplex algorithm for linear programming, perhaps the most important algorithm developed in the 20th century. This paper traces a single historical thread: Dantzig's work on linear programming and its application and extension to combinatorial optimization, and the investigations it has stimulated about the performance of the simplex algorithm and the intrinsic complexity of linear programming and combinatorial optimization.