George Dantzig's impact on the theory of computation

DOI10.1016/j.disopt.2006.12.004zbMath1151.90527OpenAlexW1965311270MaRDI QIDQ951091

Richard M. Karp

Publication date: 29 October 2008

Published in: Discrete Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.disopt.2006.12.004

zbMATH Keywords

computational complexitylinear programminginteger programmingcombinatorial optimizationsimplex algorithmpolynomial-time algorithm

Mathematics Subject Classification ID

Integer programming (90C10) Linear programming (90C05) Combinatorial optimization (90C27) Extreme-point and pivoting methods (90C49)

Related Items

Novel interior point algorithms for solving nonlinear convex optimization problems

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A new polynomial-time algorithm for linear programming
• A strongly polynomial minimum cost circulation algorithm
• A simplex variant solving an m\(\times d\) linear program in O(min(m 2,d 2)) expected number of pivot steps
• Implementing the Dantzig-Fulkerson-Johnson algorithm for large traveling salesman problems
• PRIMES is in P
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• On the Shortest Route Through a Network
• A randomized polynomial-time simplex algorithm for linear programming
• On the average number of steps of the simplex method of linear programming
• Outline of an algorithm for integer solutions to linear programs
• On the Significance of Solving Linear Programming Problems with Some Integer Variables
• Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
• Smoothed analysis of algorithms
• Improved asymptotic analysis of the average number of steps performed by the self-dual simplex algorithm
• A simplex algorithm whose average number of steps is bounded between two quadratic functions of the smaller dimension
• A quasi-polynomial bound for the diameter\\of graphs of polyhedra
• Polynomial expected behavior of a pivoting algorithm for linear complementarity and linear programming problems
• Paths, Trees, and Flowers
• Solution of a Large-Scale Traveling-Salesman Problem
• The complexity of theorem-proving procedures