A deterministic poly(log log N)-time N-processor algorithm for linear programming in fixed dimension

ABSTRACT

It is shown that for any fixed number of variables, the linear programming problems with n linear inequalities can be solved deterministically by n parallel processors in sub-logarithmic time. The parallel time bound is O((log log n)d) where d is the number of variables. In the one-dimensional case this bound is optimal.

REFERENCES

• 1: Miklós Ajtai , János Komlós , W. L. Steiger , Endre Szemerédi, Optimal parallel selection had complexity O(log log N), Journal of Computer and System Sciences, v.38 n.1, p.125-133, February 1989 [doi>10.1016/0022-0000(89)90035-4]
• 2: N. Alon and N. Megiddo, "Parallel linear programrning in fixed dimension almost surely in constant time," in: Proceedings of the 31st IEEE Symposium on Foundations of Computer Science (1990), IEEE Computer Society Press, Los Angeles, 1990, pp. 574-582.
• 3: 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]
• 4: X. Deng, An optimal parallel algorithm for linear programming in the plane, Information Processing Letters, v.35 n.4, p.213-217, Aug. 1990 [doi>10.1016/0020-0190(90)90026-T]
• 5: D. Dobkin, R. J. Lipton, and S. Reiss, "Linear programming is log space hard for P," Information Processin# Letters 8 (1979) 96-97.
• 6: M. E. Dyer, "Linear time algorithms for two- and three-variable linear programs," SIAM J. Comput. 13 (1984) 31-45.
• 7: 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]
• 8: A. Lubotzky, it. Phillips, and P. Sarnak, "Explicit expanders and the Ramanujan conjectures," Com- #inatorica 8 (1988) 261-277.
• 9: N. Megiddo, "Linear-time algorithms for linear programming in R3 and related problems," SIAM J. Comlout. 12 (1983) 759-776.
• 10: 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]
• 11: N. Megiddo, "Dynamic location problems," An-
• 12: R. M. Tanner, "Explicit concentrators from genera2ized N-gons," SIAM J. A Iu. Disc. Math. 5 (1984) 287-293.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.2 Modes of Computation
          Subjects: Parallelism and concurrency

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY

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

General Terms:
Algorithms, Performance, Theory