AbstractThis paper gives an algorithm for solving linear programming problems. For a problem with n constants and d variables, the algorithm requires an expected
O(d^2 n) + (log n)O(d)^{d/2 + O(1)} + O(d \sqrt[4]{n} log n)
arithmetic operations, as n --> \infty. The constant factors do not depend on d. Also, an algorithm is given for integer linear programming. Let \varphi bound the number of bits required to specify the rational numbers, defining an input constraint or the objective function vector. Let n and d be as before. Then, the algorithm requires expected
O(2^d dn + 8^d d\sqrt{n ln n} ln n) + d^{O(d)}\varphi ln n
operations on numbers with d^{O(1)}\varphi bits, as n --> \infty, where the constant factors do not depend on d or \varphi. The expectations are with respect to the random choices made by the algorithms, and the bounds hold for any given input. The technique can be extended to other convex programming problems. For example, an algorithm for finding the smallest sphere enclosing a set of n points in E^d has the same time bound. Copyright 1995 by ACM, Inc.
The abstract is also available as a LaTeX file, a DVI file, or a PostScript file.
Categories and Subject Descriptors: G.1.6 [Numerical Analysis]: Optimization; G.3 [Probability and Statistics]
General Terms: Algorithms, Theory
Selected papers that cite this one
- Timothy M. Chan. Deterministic algorithms for 2-d convex programming and 3-d online linear programming. In Proceedings of the Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 464-472, New Orleans, Louisiana, 5-7 January 1997.
- Timothy M. Chan. Deterministic algorithms for 2-d convex programming and 3-d online linear programming. Journal of Algorithms, 27(1):147-166, April 1998.
- Bernd Gärtner. Exact arithmetic at low cost -- a case study in linear programming. In Proceedings of the Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 157-166, San Francisco, California, 25-27 January 1998.
- J. Matou\v{s}ek, M. Sharir, and E. Welzl. A subexponential bound for linear programming. Algorithmica, 16(4/5):498-516, October/November 1996.
Selected references
- Noga Alon and Nimrod Megiddo. Parallel linear programming in fixed dimension almost surely in constant time. In 31st Annual Symposium on Foundations of Computer Science, volume II, pages 574-582, St. Louis, Missouri, 22-24 October 1990. IEEE.
- Sidnie Dresher Feit. A fast algorithm for the two-variable integer programming problem. Journal of the ACM, 31(1):99-113, January 1984.
- Gil Kalai. A subexponential randomized simplex algorithm (extended abstract). In Proceedings of the Twenty-Fourth Annual ACM Symposium on the Theory of Computing, pages 475-482, Victoria, British Columbia, Canada, 4-6 May 1992.
- Nick Littlestone. Learning quickly when irrelevant attributes abound: A new linear-threshold algorithm (extended abstract). In 28th Annual Symposium on Foundations of Computer Science, pages 68-77, Los Angeles, California, 12-14 October 1987. IEEE.
- Nimrod Megiddo. Linear programming in linear time when the dimension is fixed. Journal of the ACM, 31(1):114-127, January 1984.