A subexponential bound for linear programming

ABSTRACT

We present a simple randomized algorithm which solves linear programs with n constraints and d variables in expected O(nde(d ln(n+1))1/4) time in the unit cost model (where we count the number of arithmetic operations on the numbers in the input). The expectation is over the internal randomizations performed by the algorithm, and holds for any input. The algorithm is presented in an abstract framework, which facilitates its application to several other related problems. The algorithm has been presented in a previous work by the authors [ShW], but its analysis and the subexponential complexity bound are new.

REFERENCES

• Beh: F. Behrend, Uber die kleinste umbeschriebene und die grStlte einbeschriebene Ellipse eines konvexen Bereiches, Math. Ann. 115 (1938), 379-411.
• Cha: Bernard Chazelle, An optimal convex hull algorithm and new results on cuttings (extended abstract), Proceedings of the 32nd annual symposium on Foundations of computer science, p.29-38, September 1991, San Juan, Puerto Rico [doi>10.1109/SFCS.1991.185345]
• Cla1: K L Clarkson, Linear programming in O(n × 3d2) time, Information Processing Letters, v.22 n.1, p.21-24, January 2, 1986 [doi>10.1016/0020-0190(86)90037-2]
• Cla2: K.L. Clarkson, Las Vegas algorithms for linear and integer programming when the dimension is small, manuscript, 1989.
• DLL: L. Danzer, D. Laugwitz and H. Lenz, /~Iber das LSwnersche Ellipsoid und sein Analogon unter den einem EikSrper eingeschriebenen Ellipsoiden, Arch. Math. 8 (1957), 214-219.
• Dan: D.B. Dantzig, Linear Programming and Extensions, Princeton University Press, Princeton, N.J., 1963.
• Dye1: M E Dyer, On a multidimensional search technique and its application to the Euclidean one centre problem, SIAM Journal on Computing, v.15 n.3, p.725-738, August 1986 [doi>10.1137/0215052]
• Dye2: Martin Dyer, A class of convex programs with applications to computational geometry, Proceedings of the eighth annual symposium on Computational geometry, p.9-15, June 10-12, 1992, Berlin, Germany [doi>10.1145/142675.142681]
• DyF: M.E. Dyer ~md A. M. Frieze, A randomized algorithm for fixed-dimensional linear programming, manuscript, 1987.
• Gär: B. G/irtner, manuscript in preparation, M~rch 1992.
• Juh: F. Juhnke, LSwner ellipsoids via semiinfinite optimization and (quasi-) convexity theory, Technische Universit/it Magdeburg, Sektion Mathematik, Report 4/90 (1990).
• Jun: H. Jung, 0ber die kleinste Kugel, die eine r/iumhche Figur einschlietlt, J. Reine Angew. Math. 123 (1901), 241-257.
• Kal: Gil Kalai, A subexponential randomized simplex algorithm (extended abstract), Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.475-482, May 04-06, 1992, Victoria, British Columbia, Canada [doi>10.1145/129712.129759]
• Kar: N. Karmarkar, A new polynomial-time algorithm for linear programming, Combinatorica, v.4 n.4, p.373-395, Dec. 1984 [doi>10.1007/BF02579150]
• Kha: L.G. Khachiyan, Polynomial algorithm in linear programming, U.S.S.R. Gomput. Math. and Math. Phys. 20 (1980), 53-72.
• KlM: V. Klee and G.J. Minty, How good is the simplex algorithm, Inequalities III, pp. 159-175, O. Shisha (ed.) Academic Press, New-York, 1972.
• Meg: Nimrod Megiddo, Linear Programming in Linear Time When the Dimension Is Fixed, Journal of the ACM (JACM), v.31 n.1, p.114-127, Jan. 1984 [doi>10.1145/2422.322418]
• Pos: Mark J. Post, Minimum spanning ellipsoids, Proceedings of the sixteenth annual ACM symposium on Theory of computing, p.108-116, December 1984 [doi>10.1145/800057.808672]
• Sei1: Raimund Seidel, Small-dimensional linear programming and convex hulls made easy, Discrete & Computational Geometry, v.6 n.5, p.423-434, 1991 [doi>10.1007/BF02574699]
• Sei2: R. Seidel, Backwards analysis of randomized algorithms, manuscript, 1991.
• ShW: Micha Sharir , Emo Welzl, A Combinatorial Bound for Linear Programming and Related Problems, Proceedings of the 9th Annual Symposium on Theoretical Aspects of Computer Science, p.569-579, February 13-15, 1992
• Wel: E. Welzl, Smallest enclosing disks (balls and ellipsoids), in "New Results and New Trends in Computer Science", (H. Maurer, Ed.), Lecture Notes in Computer Science 555 (1991), 359-370.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.6 Optimization
          Subjects: Linear programming

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Geometrical problems and computations

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.1 Combinatorics
          Subjects: Combinatorial algorithms
  G.3 PROBABILITY AND STATISTICS
      Subjects: Probabilistic algorithms (including Monte Carlo)

General Terms:
Algorithms

Keywords:
combinatorial optimization, computational geometry, linear programming, randomized incremental algorithms