Journal of the Association for Computing Machinery, Vol. 42, No. 2, March 1995, pp. 488–499.

Las Vegas Algorithms for Linear and Integer Programming When the Dimension is Small

KENNETH L. CLARKSON

Abstract. 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 ^{4} \sqrt{n} log n)

arithmetic operations, as n → ∞. The constant factors do not depend on d. Also, an algorithm is given for integer linear programming. Let φ 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)}φ ln n

operations on numbers with d^{O(1)}φ bits, as n → ∞, where the constant factors do not depend on d or φ. 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.

Categories and Subject Descriptors. G.1.6[integer programming, nonlinear programming]; G.3

General Terms. Algorithms, Theory

Copyright 1995 by ACM, Inc. Permission to make digital or hard copies of part or all of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or direct commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, to republish, to post on servers, or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from Publications Dept, ACM Inc., fax +1 (212) 869-0481, or permissions@acm.org.