In 1972, Klee and Minty demonstrated the existence of a problem in this field which had an exponential running time of 2 raised to the n for a cube in n dimensions.
In 1972, Klee and Minty demonstrated the existence of a problem in this field which had an exponential running time of 2 raised to the n for a cube in n dimensions. A polynomial-time algorithm in this field was developed by Khachiyan and is known as the ellipsoid method; that algorithm in this field is known as an "interior-path" algorithm. Another interior-path algorithm which finds the analytic center, a point that minimizes the potential function,(*) was developed for solving problems in this field by Karmarkar. A common algorithm for solving problems in this field involves moving between extreme points of the objective function in such a way that the objective function either increases or stays the same; that method was developed in 1947 by George Dantzig and is known as the simplex algorithm. For 10 points, identify this field of optimization theory that is concerned with solving problems in which the unknowns as well as the constraints are all of monomial degree.
In 1972, Klee and Minty demonstrated the existence of a problem in this field which had an exponential running time of 2 raised to the n for a cube in n dimensions.
linear programming [prompt on "optimization"]