Abstract
This is a review of the literature on parallel computers and algorithms that is relevant for combinatorial optimization. We start by describing theoretical as well as realistic machine models for parallel computations. Next, we deal with the complexity theory for parallel computations and illustrate the resulting concepts by presenting a number of polylog parallel algorithms andP-completeness results. Finally, we discuss the use of parallelism in enumerative methods.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
M. Ajtai, J. Komlós andE. Szemerédi, Sorting inclogn parallel steps, Combinatorica 3 (1983) 1–19.
H. Alt, T. Hagerup, K. Mehlhorn andF.P. Preparata, Deterministic simulation of idealized parallel computers on more realistic ones, eds.J. Gruska, B. Rovan, J. Wiedermann,Mathematical Foundations of Computer Science 1986, Lecture Notes in Computer Science 233 (Springer, Berlin, 1986) 199–208.
B. Awerbuch, A. Israeli andY. Shiloach, Finding Euler circuits in logarithmic parallel time, Proc. 16th Annual ACM Symp. Theory of Computing (1984) 249–257.
R.E. Bellman,Dynamic Programming (Princeton University Press, Princeton, NJ, 1957).
R.E. Bellman andS.E. Dreyfus,Applied Dynamic Programming (Princeton University Press, Princeton, NJ, 1962).
J.L. Bentley, A parallel algorithm for constructing minimum spanning trees, J. Algorithms 1 (1980) 51–59.
J.L. Bentley andH.T. Kung, A tree machine for searching problems, Proc. 1979 Internat. Conf. Parallel Processing (1979) 257–266.
C. Berge andA. Ghouila-Houri,Programmes, Jeux et Réseaux de Transports (Dunod, Paris, 1962).
O.J. Boxma andG.A.P. Kindervater,A Queueing Network Model for Analyzing a Class of Branch and Bound Algorithms on a Master-Slave Architecture, Report OS-R8717 (Centre for Mathematics and Computer Science, Amsterdam, 1987).
F.W. Burton, M.M. Huntbach, G.P. McKeown andV.J. Rayward-Smith,Parallelism in Branch-and-Bound Algorithms, Report CSA/3/1983 (University of East Anglia, Norwich, 1983).
J. Casti, M. Richardson andR. Larson, Dynamic programming and parallel computers, J. Optim. Theory Appl. 12 (1973) 423–438.
A.K. Chandra, D.C. Kozen andL.J. Stockmeyer, Alternation, J. Assoc. Comput. Mach. 28 (1981) 114–133.
L. Csanky, Fast parallel matrix inversion algorithms, SIAM J. Comput. 5 (1976) 616–623.
S.A. Cook, An observation on time-storage trade off, J. Comput. System Sci. 9 (1974) 308–316.
S.A. Cook, Towards a complexity theory of synchronous parallel computation, Enseign. Math. (2) 27 (1981) 99–124.
E. Dekel, D. Nassimi andS. Sahni, Parallel matrix and graph algorithms, SIAM J. Comput. 10 (1981) 657–675.
E. Dekel andS. Sahni, Binary trees and parallel scheduling algorithms, IEEE Trans. Comput. C-32 (1983) 307–315.
E. Dekel andS. Sahni, Parallel scheduling algorithms, Oper. Res. 31 (1983) 24–49.
P. Di Chio andV. Zecca,IBM ECSEC Facilities: User's Guide, Report G513-4080 (IBM European Center for Scientific and Engineering Computing, Rome, 1985).
E.W. Dijkstra, A note on two problems in connexion with graphs, Numer. Math. 1 (1959) 269–271.
D. Dobkin, R.J. Lipton andS. Reiss, Linear programming is log-space hard forP, Inform. Process. Lett. 8 (1979) 96–97.
J. Edmonds andR.M. Karp, Theoretical improvements in algorithmic efficiency for network flow problems, J. Assoc. Comput. Mach. 19 (1972) 248–264.
O.I. El-Dessouki andW.H. Huen, Distributed enumeration on between computers, IEEE Trans. Comput. C-29 (1980) 818–825. Note: in the title, read ‘network’ for ‘between’.
M.J. Flynn, Very high-speed computing systems, Proc. IEEE 54 (1966) 1901–1909.
T.J. Gardner, I.M. Gerard, C.R. Mowers, E. Nemeth andR.B. Schnabel,DPUP: a Distributed Processing Utilities Package, Report CU-CS-337-86 (University of Colorado, Boulder, 1986).
M.R. Garey andD.S. Johnson,Computers and Intractability: a Guide to the Theory of NP-Completeness (Freeman, San Francisco, 1979).
L.M. Goldschlager, The monotone and planar circuit value problems are log space complete forP, SIGACT News 9.2 (1977) 25–29.
L.M. Goldschlager, A universal connection pattern for parallel computers, J. Assoc. Comput. Mach. 29 (1982) 1073–1086.
L.M. Goldschlager, R.A. Shaw andJ. Staples, The maximum flow problem is log space complete forP, Theoret. Comput. Sci. 21 (1982) 105–111.
T. Gonzalez andS. Sahni, Preemptive scheduling of uniform processor systems, J. Assoc. Comput. Mach. 25 (1978) 92–101.
L.J. Guibas, H.T. Kung andC.D. Thompson, Direct VLSI implementation of combinatorial algorithms, Caltech Conf. VLSI (1979) 509–525.
U.I. Gupta, D.T. Lee andJ.Y.-T. Leung, An optimal solution for the channel-assignment problem, IEEE Trans. Comput. C-28 (1979) 807–810.
J.R. Gurd, C.C. Kirkham andI. Watson, The Manchester prototype dataflow computer, Comm. ACM 28 (1985) 34–52.
D. Helmbold andE. Mayr,Fast Scheduling Algorithms on Parallel Computers, Report CS-84-1025 (Stanford University, CA, 1984).
R.W. Hockney andC.R. Jesshope,Parallel Computers: Architecture, Programming and Algorithms (Hilger, Bristol 1981).
D.B. Johnson, Parallel algorithms for minimum cuts and maximum flows in planar networks, J. Assoc. Comput. Mach. 34 (1987) 950–967.
D.S. Johnson, The NP-completeness column: an ongoing guide; seventh edition, J. Algorithms 4 (1983) 189–203.
A.R. Karlin andE. Upfal, Parallel hashing — an efficient implementation of shared memory (preliminary version), Proc. 18th Annual ACM Symp. Theory of Computing (1986) 160–168.
R.M. Karp, E. Upfal, andA. Wigderson, Constructing a perfect matching is in Random NC, Combinatorica 6 (1986) 35–48.
L.G. Khachian, A polynomial algorithm in linear programming, Soviet Math. Dokl. 20 (1979) 191–194.
G.A.P. Kindervater, A parallel branch and bound algorithm for the job shop problem, presentation, 8th European Conference on Operational Research, Lisbon, September 15–19, 1986.
G.A.P. Kindervater andJ.K. Lenstra, Parallel algorithms, eds.M. O'hEigeartaigh, J.K. Lenstra andA.H.G. Rinnooy Kan,Combinatorial Optimization: Annotated Bibliographies (Wiley, Chichester, 1985) Ch. 8.
G.A.P. Kindervater andJ.K. Lenstra, An introduction to parallelism in combinatorial optimization, Discrete Appl. Math. 14 (1986) 135–156.
G.A.P. Kindervater andJ.K. Lenstra,The Parallel Complexity of TSP Heuristics, Report OS-R8609 (Centre for Mathematics and Computer Science, Amsterdam, 1986).
G.A.P. Kindervater andH.W.J.M. Trienekens, Experiments with parallel algorithms for combinatorial problems, European J. Oper. Res. 33 (1988) 65–81.
R.E. Ladner, The circuit value problem is log space complete forP, SIGACT News 7.1 (1975) 18–20.
B.J. Lageweg, J.K. Lenstra andA.H.G. Rinnooy Kan, Job-shop scheduling by implicit enumeration, Management Sci. 24 (1977) 441–450.
T.-H. Lai andS. Sahni, Anomalies in parallel branch-and-bound algorithms, Comm. ACM 27 (1984) 594–602.
T.-H. Lai andA. Sprague, Performance of parallel branch-and-bound algorithms, IEEE Trans. Comput. C-34 (1985) 962–964.
T.-H. Lai andA. Sprague, A note on anomalies in parallel branch-and-bound algorithms with one-to-one bounding functions, Inform. Process. Lett. 23 (1986) 119–122.
E.L. Lawler,Combinatorial Optimization: Networks and Matroids (Holt, Rinehart and Winston, New York, 1976).
E.L. Lawler, J.K. Lenstra, A.H.G. Rinnooy Kan andD.B. Shmoys, eds.,The Traveling Salesman Problem: a Guided Tour of Combinatorial Optimization (Wiley, Chichester, 1985).
G.-J. Li andB.W. Wah, Coping with anomalies in parallel branch-and-bound algorithms, IEEE Trans. Comput. C-35 (1986) 568–573.
L. Lovász, Determinants, matchings and random algorithms, ed.L. Budach,Fundamentals of Computing Theory, FCT '79 (Akademie Verlag, Berlin, 1979) 565–574.
C.U. Martel,A Parallel Algorithm for Preemptive Scheduling of Uniform Machines, Preprint (University of California, Davis, CA, 1986).
R. McNaughton, Scheduling with deadlines and loss function, Management Sci. 6 (1959) 1–12.
N. Megiddo,Poly-log Parallel Algorithms for LP with an Application to Exploding Flying Objects (1982) unpublished manuscript.
D.E. Muller andF.P. Preparata, Bounds to complexities of networks for sorting and for switching, J. Assoc. Comput. Mach. 22 (1975) 195–201.
J.F. Muth andG.L. Thompson, eds.,Industrial Scheduling (Prentice Hall, Englewood Cliffs, NJ, 1963), 237.
F.P. Preparata andJ. Vuillemin, The cube-connected cycles: a versatile network for parallel computation, Comm. ACM 24 (1981) 300–309.
R.C. Prim, Shortest connection networks and some generalizations, Bell System Tech. J. 36 (1957) 1389–1401.
E.A. Pruul,Parallel Processing and a Branch-and-Bound Algorithm, M.Sc. thesis (Cornell University, Ithaca, NY, 1975).
C. Savage andJ. Ja'Ja', Fast, efficient parallel algorithms for some graph problems, SIAM J. Comput. 10 (1981) 682–691.
J.T. Schwartz, Ultracomputers, ACM Trans. Programming Languages and Systems 2 (1980) 484–521.
H.J. Siegel, Analysis techniques for SIMD machine interconnection networks and the effects of processor address masks, IEEE Trans. Comput. C-26 (1977) 153–161.
H.J. Siegel, A model of SIMD machines and a comparison of various interconnection networks, IEEE Trans. Comput. C-28 (1979) 907–917.
J.S. Squire andS.M. Palais, Programming and design considerations of a highly parallel computer, Proc. AFIPS Spring Joint Computer Conf. 23 (1963) 395–400.
H.S. Stone, Parallel processing with the perfect shuffle, IEEE Trans. Comput. C-20 (1971) 153–161.
H.W.J.M. Trienekens,Parallel Branch and Bound on an MIMD System, Report 8640/A (Econometric Institute, Erasmus University, Rotterdam, 1986).
S.H. Unger, A computer oriented toward spatial problems, Proc. IRE 46 (1958) 1744–1750.
E. Upfal, A probabilistic relation between desirable and feasible models of parallel computation (preliminary version), Proc. 16th Annual ACM Symp. Theory of Computing (1984) 258–265.
L.G. Valiant, Reducibility by algebraic projections, Enseign. Math. (2) 28 (1982) 253–268.
P. van Emde Boas, The second machine class: models of parallelism, eds.J. van Leeuwen andJ.K. Lenstra,Parallel Computers and Computations (CWI Syllabus 9, Centre for Mathematics and Computer Science, Amsterdam, 1985), 133–161.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Kindervater, G.A.P., Lenstra, J.K. Parallel computing in combinatorial optimization. Ann Oper Res 14, 245–289 (1988). https://doi.org/10.1007/BF02186483
Issue Date:
DOI: https://doi.org/10.1007/BF02186483