Journal of the ACM Bibliography

Kenneth L. Clarkson. Las Vegas algorithms for linear and integer programming when the dimension is small. Journal of the ACM, 42(2):488-499, March 1995. [BibTeX entry]

This 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

Selected references


  • Journal of the ACM homepage
  • Bibliography top level
  • Journal of the ACM Author Index
  • Search the HBP database