Miklos Ajtai
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.
- 1.M. Ajtai, j. Koml6s, W. L. Steiger, and E. Szemer#di, "Optimal parallel selection has complexity O(IoglogN)," J. Comp. Sys. Sci. 38 (1989) 125-133. Google Scholar
Digital Library
- 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.Google Scholar
- 3.K. L. Clarkson, "Linear programming in O(n x 3#) time," Information Processing Letters 22 (1986) 21-27. Google ScholarDigital Library
- 4.X. Deng, "An optimal parallel algorithm for linear programming in tire plane," Injormation Processing Letters 35 (1990) 213-217. Google ScholarDigital Library
- 5.D. Dobkin, R. J. Lipton, and S. Reiss, "Linear programming is log space hard for P," Information Processin# Letters 8 (1979) 96-97.Google ScholarCross Ref
- 6.M. E. Dyer, "Linear time algorithms for two- and three-variable linear programs," SIAM J. Comput. 13 (1984) 31-45.Google ScholarCross Ref
- 7.M. E. Dyer, "On a multidimensional search technique #nd its #ppllc#tion to the Euclidean onecenter problem," SIAM I. Comput. 15 (1986) 725-738. Google ScholarDigital Library
- 8.A. Lubotzky, it. Phillips, and P. Sarnak, "Explicit expanders and the Ramanujan conjectures," Com- #inatorica 8 (1988) 261-277.Google ScholarCross Ref
- 9.N. Megiddo, "Linear-time algorithms for linear programming in R3 and related problems," SIAM J. Comlout. 12 (1983) 759-776.Google ScholarCross Ref
- 10.N. Megiddo, "Linear programming in linear time when the dimension is #xed," jr. A CM 31 (1984) 114-127. Google ScholarDigital Library
- 11.N. Megiddo, "Dynamic location problems," An-Google Scholar
- 12.R. M. Tanner, "Explicit concentrators from genera2ized N-gons," SIAM J. A Iu. Disc. Math. 5 (1984) 287-293.Google ScholarCross Ref
Index Terms
- A deterministic poly(log log N)-time N-processor algorithm for linear programming in fixed dimension
Recommendations
A Deterministic poly(log log N)-Time N-Processor Algorithm for Linear Programming in Fixed Dimension
It is shown that for any fixed number of variables, linear-programming problems with $n$ linear inequalities can be solved deterministically by $n$ parallel processors in sublogarithmic time. The parallel time bound (counting only the arithmetic ...
Fully dynamic connectivity in O(log n(log log n)2) amortized expected time
SODA '17: Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete AlgorithmsDynamic connectivity is one of the most fundamental problems in dynamic graph algorithms. We present a new randomized dynamic connectivity structure with O(log n(log log n)2) amortized expected update time and O(log n/log log log n) query time, which ...
On Linear-Time Deterministic Algorithms for Optimization Problems in Fixed Dimension
We show that with recently developed derandomization techniques, one can convert Clarkson's randomized algorithm for linear programming in fixed dimension into a linear-time deterministic algorithm. The constant of proportionality isdO(d), which is ...
Comments