1984 · 1K citations · 4 references
Natural SciencesComputer ScienceAlgorithmsGeometryOptimizationApproximation AlgorithmsCombinatorial OptimizationConvex OptimizationGeometric OptimizationLinear ProgrammingPolynomial OptimizationPolynomial Time ComplexityPolynomial-time AlgorithmsProjective TransformationsTransformations
We present a new polynomial-time algorithm for linear programming. The running-time of this algorithm is O(n3-5L2), as compared to O(n6L2) for the ellipsoid algorithm. We prove that given a polytope P and a strictly interior point a ε P, there is a projective transformation of the space that maps P, a to P', a' having the following property. The ratio of the radius of the smallest sphere with center a', containing P' to the radius of the largest sphere with center a' contained in P' is O (n). The algorithm consists of repeated application of such projective transformations each followed by optimization over an inscribed sphere to create a sequence of points which converges to the optimal solution in polynomial-time.
4
HOW GOOD IS THE SIMPLEX ALGORITHM
Victor Klee, George J. Minty · 1970 · 784 citations
G. M. Petersen, H. S. M. Coxeter · American Mathematical Monthly · 1961 · 548 citations