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

ABSTRACT

This paper gives an algorithm for solving linear programming problems. For a problem with n constraints and d variables, the algorithm requires an expectedOd²n+lognOd^d/2+O1+Od⁴nlogn 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 O2^ddn+8^ddnl nnlnn +d^od4 lnn operations on numbers with d^o14 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 E^dhas the same time bound.

REFERENCES

• 1: ~ADLER, I. ~,ND SIIAMIR, R. 1990. A randomization scheme for speeding up algorithms for linear ~and convex quadratic programming problems with a high constraints-to-variables ratio. Tech. ~Rep. 21-90, Rutgers Univ., Rutgers, N.J., May. (Math. Prog. to appear.)
• 2: ~ALON, N. AND MEGIDDO, N. 1990. Parallel linear programming m fixed dimension almost surely ~in constant time. In Proceedings of the 3}st IEEE Symposium on Fouttdations of Compztter ~Sctence. IEEE, New York, pp. 574 582.
• 3: L Babai, On Lova´sz' lattice reduction and the nearest lattice point problem, Proceedings on STACS 85 2nd annual symposium on theoretical aspects of computer science, p.13-20, December 1985, Saarbru:9Aicken, Germany
• 4: ~BELL, D. E. 1977. A theorem concerning the integer lattice. Stud. Appl. Math. 56, 187-188.
• 5: ~CHARNES, A. 1952. Optimality and degeneracy in linear programming. Econometrika 20, 160-170.
• 6: Bernard Chazelle , Jiří Matoušek, On linear-time deterministic algorithms for optimization problems in fixed dimension, Proceedings of the fourth annual ACM-SIAM Symposium on Discrete algorithms, p.281-290, January 25-27, 1993, Austin, Texas, United States
• 7: K L Clarkson, Linear programming in O(n × 3d2) time, Information Processing Letters, v.22 n.1, p.21-24, January 2, 1986 [doi>10.1016/0020-0190(86)90037-2]
• 8: CLARKSON, K. L. 1987. New applications of random sampling in computational geometry. Disc. ~Comput. Geometry 2, 195-222.
• 9: K. L. Clarkson , P. W. Shor, Applications of random sampling in computational geometry, II, Discrete & Computational Geometry, v.4 n.5, p.387-421, 1989 [doi>10.1007/BF02187740]
• 10: M E Dyer, On a multidimensional search technique and its application to the Euclidean one centre problem, SIAM Journal on Computing, v.15 n.3, p.725-738, August 1986 [doi>10.1137/0215052]
• 11: M. E. Dyer , A. M. Frieze, A randomized algorithm for fixed-dimensional linear programming, Mathematical Programming: Series A and B, v.44 n.2, p.203-212, 1989 [doi>10.1007/BF01587088]
• 12: Sidnie Dresher Feit, A Fast Algorithm for the Two-Variable Integer Programming Problem, Journal of the ACM (JACM), v.31 n.1, p.99-113, Jan. 1984 [doi>10.1145/2422.322417]
• 13: A. Frank , Éva Tardos, An application of simultaneous Diophantine approximation in combinatorial optimization, Combinatorica, v.7 n.1, p.49-65, Jan. 1987 [doi>10.1007/BF02579200]
• 14: ~GILL, P. E., MURRAY, W., AND WRIGHT, M. H. 1981. Practical Optimtzatton. Academic Press, ~Orlando, Fla.
• 15: ~GILL, P. E., MURRAY, W., AND WRIGHT, M. H. 1991. Numerical Linear Algebra and Optimization. ~Addison-Wesley, New York.
• 16: ~HAUSSLER, D., AND WELZL, E. 1987. Epsilon-nets and simplex range queries. Dtsc. Comput. ~Geometry 2, 127-151.
• 17: Gil Kalai, A subexponential randomized simplex algorithm (extended abstract), Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.475-482, May 04-06, 1992, Victoria, British Columbia, Canada [doi>10.1145/129712.129759]
• 18: Ravi Kannan, Minkowski's convex body theorem and integer programming, Mathematics of Operations Research, v.12 n.3, p.415-440, August 1, 1987 [doi>10.1287/moor.12.3.415]
• 19: ~KHACHIAN, L. G. 1980. Polynomial algorithms in linear programming, Z. Vych. Math. Mat. Fiz., ~53-72.
• 20: ~KLEE, g., AND MINTY, G. J. 1972. HOW good is the simplex algorithm? In Inequalities III. ~Academic Press, Orlando, Fla.
• 21: ~LENSTRA, H. W. 1983. Integer programming with a fixed number of variables. Math. Oper. Res., ~538-548.
• 22: ~LITTLESTONE, N. Learning quickly when irrelevant attributes abound: A new linear-threshold ~algorithm. In Proceedings of the 28th IEEE Sympostum on Foundattons of Computer Science. ~IEEE, New York, pp. 68-77.
• 23: Nimrod Megiddo, Linear Programming in Linear Time When the Dimension Is Fixed, Journal of the ACM (JACM), v.31 n.1, p.114-127, Jan. 1984 [doi>10.1145/2422.322418]
• 24: Jiří Matoušek , Micha Sharir , Emo Welzl, A subexponential bound for linear programming, Proceedings of the eighth annual symposium on Computational geometry, p.1-8, June 10-12, 1992, Berlin, Germany [doi>10.1145/142675.142678]
• 25: ~SCARF, H. E. 1977. An observation on the structure of production sets with indivisibilities. In ~Proceedings of the National Academy of Sciences of the United States of America 74, 3637-3641.
• 26: Alexandeer Schrijver, Theory of linear and integer programming, John Wiley & Sons, Inc., New York, NY, 1986
• 27: Raimund Seidel, Small-dimensional linear programming and convex hulls made easy, Discrete & Computational Geometry, v.6 n.5, p.423-434, 1991 [doi>10.1007/BF02574699]
• 28: ~SPENCER, J. 1974. Puncture sets. J. Combm. Theory A 17, 329-336.
• 29: Jeffrey Scott Vitter, Faster methods for random sampling, Communications of the ACM, v.27 n.7, p.703-718, July 1984 [doi>10.1145/358105.893]
• 30: E. Welzl, Partition trees for triangle counting and other range searching problems, Proceedings of the fourth annual symposium on Computational geometry, p.23-33, June 06-08, 1988, Urbana-Champaign, Illinois, United States [doi>10.1145/73393.73397]

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.6 Optimization
          Subjects: Linear programming

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.6 Optimization
          Subjects: Integer programming

General Terms:
Algorithms, Theory