On parallel complexity of integer linear programming, GCD and the iterated mod function

ABSTRACT

We study parallel computational methods for integer linear programming problem with two variables. Applying several novel techniques, we prove that this problem is NC-equivalent to computing the continued fraction expansion of a rational number, that is, to computing all the intermediate remainders in the Euclidean algorithm applied to two integers, plus to computing the output of an iterated modulo function, with the remainder sequence from the Euclidean algorithm (that is, with the continued fraction expansion of a rational number) as its input arguments. The best previously known results are special cases of our theorem.

REFERENCES

• ACGOY: Aggarwal, A., Chazelle, B., Guibas, L., O'Dunlaing, C., Yap, C., "Parallel computational geometry", 26th IEEE Symp. on the Foundations of Computer Science, pp. 486-474, 1985.
• AHU: Alfred V. Aho , John E. Hopcroft, The Design and Analysis of Computer Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1974
• Akl: Selim G. Akl, Parallel Sorting Algorithms, Academic Press, Inc., Orlando, FL, 1990
• AKS: M. Ajtai , J. Komlós , E. Szemerédi, An 0(n log n) sorting network, Proceedings of the fifteenth annual ACM symposium on Theory of computing, p.1-9, December 1983 [doi>10.1145/800061.808726]
• AM: Alon, N., Meggido, N., "Parallel linear programming in fixed dimension almost surely in constant time", Proc. 32nd Annual IEEE Syrup. on Foundations of Comp. Sci., 1990, pp. 574-582.
• AnMa: Anderson, RJ., Mayr, E.W., 'Parallel and greedy algorithm", Advances in Computing Research, 4 (Parallel and Distributed Computing), ed. F.P. Preparata, pp. 17-38, 1987.
• BP: Bini, D., Pan, V., Numerical and Algebraic Compu. tations with Matrices and Polynomials, Birkhauser, Boston, to a~ in 1991.
• De1: Xiaotie Deng , Christos H. Papadimitriou, Mathematical programming: complexity and applications, 1989
• De2: X. Deng, On the parallel complexity of integer programming, Proceedings of the first annual ACM symposium on Parallel algorithms and architectures, p.110-116, June 18-21, 1989, Santa Fe, New Mexico, United States [doi>10.1145/72935.72948]
• EG: David Eppstein , Zvi Galil, Parallel algorithmic techniques for combinatorial computation, Annual review of computer science: vol. 3, 1988, Annual Reviews Inc., Palo Alto, CA, 1988
• GR: Alan Gibbons , Wojciech Rytter, Efficient parallel algorithms, Cambridge University Press, New York, NY, 1988
• HU: John E. Hopcroft , Jeffrey D. Ullman, Introduction To Automata Theory, Languages, And Computation, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1990
• Ka1: Ravindran Kannan, A Polynomial Algorithm for the Two-Variable Integer Programming Problem, Journal of the ACM (JACM), v.27 n.1, p.118-122, Jan. 1980 [doi>10.1145/322169.322179]
• Ka2: Ravi Kannan, Improved algorithms for integer programming and related lattice problems, Proceedings of the fifteenth annual ACM symposium on Theory of computing, p.193-206, December 1983 [doi>10.1145/800061.808749]
• KR: Richard M. Karp , Vijaya Ramachandran, Parallel algorithms for shared-memory machines, Handbook of theoretical computer science (vol. A): algorithms and complexity, MIT Press, Cambridge, MA, 1991
• KaRu: Howard J. Karloff , Walter L. Ruzzi, The iterated mod problem, Information and Computation, v.80 n.3, p.193-204, Mar. 1989 [doi>10.1016/0890-5401(89)90008-4]
• Knu: Donald E. Knuth, The art of computer programming, volume 2 (3rd ed.): seminumerical algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1997
• Len: Lenstra, H.W., Jr., "Integer linear programming with a fixed number of variables", Mathematics of Operations Research, vol. 8, pp. 538-548, 1983.
• Lin: Yu Lin, Parallel computational methods in integer linear programming, City University of New York, New York, NY, 1991
• Qui: Michael J. Quinn, Designing efficient algorithms for parallel computers, McGraw-Hill, Inc., New York, NY, 1987

INDEX TERMS

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

Additional Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES

General Terms:
Algorithms, Theory, Verification