Las Vegas algorithms for linear and integer programming when the dimension is small

Las Vegas algorithms for linear and integer programming when the dimension is small

0.00 Avg rating0 Votes
Article ID: iaor20012961
Country: United States
Volume: 42
Issue: 2
Start Page Number: 488
End Page Number: 499
Publication Date: Mar 1995
Journal: Journal of the Association for Computing Machinery
Authors:
Keywords: programming: integer
Abstract:

This paper gives an algorithm for solving linear programming problems. For a problem with n constraints and d variables, the algorithm requires an expected O(d2n) + (log n) O(d)d/2+O(1) + O(d4√(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(2d dn + 8dd√(n ln n) ln n) + dO(d)ϕ ln n operations on numbers with dO(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 Ed has the same time bound.

Reviews

Required fields are marked *. Your email address will not be published.