Las Vegas algorithms for linear and integer programming when the dimension is small
- 1 March 1995
- journal article
- Published by Association for Computing Machinery (ACM) in Journal of the ACM
- Vol. 42 (2) , 488-499
- https://doi.org/10.1145/201019.201036
Abstract
This paper gives an algorithm for solving linear programming problems. For a problem with n constraints and d variables, the algorithm requires an expectedOd2n+lognOdd/2+O1+Od4nlogn arithmetic operations, asn→∞. The constant factors do not depend on d. Also, an algorithm is given for integer linear programming. Let 4 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 O2ddn+8ddnl nnlnn +dod4 lnn operations on numbers with do14 bits, as n→∞ , where the constant factors do not depend on d or4to other convex programming problems. For example, an algorithm for finding the smallest sphere enclosing a set of n points in Edhas the same time bound.Keywords
This publication has 17 references indexed in Scilit:
- A randomized algorithm for fixed-dimensional linear programmingMathematical Programming, 1989
- On a Multidimensional Search Technique and Its Application to the Euclidean One-Centre ProblemSIAM Journal on Computing, 1986
- Linear programming in O(n × 3d) timeInformation Processing Letters, 1986
- Faster methods for random samplingCommunications of the ACM, 1984
- Linear Programming in Linear Time When the Dimension Is FixedJournal of the ACM, 1984
- A Fast Algorithm for the Two-Variable Integer Programming ProblemJournal of the ACM, 1984
- On Lovász' lattice reduction and the nearest lattice point problemPublished by Springer Nature ,1984
- Polynomial algorithms in linear programmingUSSR Computational Mathematics and Mathematical Physics, 1980
- Puncture setsJournal of Combinatorial Theory, Series A, 1974
- Optimality and Degeneracy in Linear ProgrammingEconometrica, 1952