George Dantzig's impact on the theory of computation

DOI10.1016/J.DISOPT.2006.12.004zbMATH Open1151.90527OpenAlexW1965311270MaRDI QIDQ951091FDOQ951091

Authors: Richard 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

Recommendations

• George B. Dantzig and systems optimization
• An extension of the fundamental theorem of linear programming
• A linear programming primer: from Fourier to Karmarkar
• George B. Dantzig: a legendary life in mathematical programming
• scientific article; zbMATH DE number 2061763

zbMATH Keywords

computational complexitylinear programmingcombinatorial optimizationinteger programmingpolynomial-time algorithmsimplex algorithm

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• A new polynomial-time algorithm for linear programming
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
• Paths, Trees, and Flowers
• Solution of a Large-Scale Traveling-Salesman Problem
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Outline of an algorithm for integer solutions to linear programs
• The complexity of theorem-proving procedures
• PRIMES is in P
• Title not available (Why is that?)
• Smoothed analysis of algorithms
• A strongly polynomial minimum cost circulation algorithm
• Title not available (Why is that?)
• On the Significance of Solving Linear Programming Problems with Some Integer Variables
• Title not available (Why is that?)
• On the shortest route through a network
• Implementing the Dantzig-Fulkerson-Johnson algorithm for large traveling salesman problems
• A simplex variant solving an m\(\times d\) linear program in O(min(m 2,d 2)) expected number of pivot steps
• A quasi-polynomial bound for the diameter\\of graphs of polyhedra
• A randomized polynomial-time simplex algorithm for linear programming
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• On the average number of steps of the simplex method of linear programming
• Title not available (Why is that?)
• 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
• Title not available (Why is that?)
• Title not available (Why is that?)
• Polynomial expected behavior of a pivoting algorithm for linear complementarity and linear programming problems

Cited In (6)

• George B. Dantzig: a legendary life in mathematical programming
• CLOUD computing risk management for server-farm repair rates, consumer load cycle, server-farm repair crew count, and additional servers
• A linear programming primer: from Fourier to Karmarkar
• An extension of the fundamental theorem of linear programming
• Novel interior point algorithms for solving nonlinear convex optimization problems
• George B. Dantzig and systems optimization

This page was built for publication: George Dantzig's impact on the theory of computation

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q951091)