An introduction to parallelism in combinatorial optimization

DOI10.1016/0166-218X(86)90057-0zbMath0593.90047MaRDI QIDQ1076605

G. A. P. Kindervater, Jan Karel Lenstra

Publication date: 1986

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

zbMATH Keywords

sortingschedulingcombinatorial optimizationtraveling salesmanbranch and boundshortest pathsparallel computersknapsackcomplexity theory for parallel computationslog space completenesspolylog parallel algorithms

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Numerical mathematical programming methods (65K05) Integer programming (90C10) Linear programming (90C05) Dynamic programming (90C39)

Related Items (16)

A polynomial approximation scheme for the subset sum problem ⋮ Some parallel algorithms on interval graphs ⋮ Branch-and-bound and parallel computation: A historical note ⋮ Parallel circle-cover algorithms ⋮ On efficient parallel computations for some dynamic programming problems ⋮ A simulation tool for the performance evaluation of parallel branch and bound algorithms ⋮ Some thoughts on combinatorial optimisation ⋮ Unnamed Item ⋮ A model classifying algorithms as inherently sequential with applications to graph searching ⋮ Parallel algorithms on circular-arc graphs ⋮ Parallel time and space upper-bounds for the subset-sum problem ⋮ An efficient parallel logarithmic time algorithm for the channel routing problem ⋮ Large-scale 0-1 linear programming on distributed workstations ⋮ Optimal parallel algorithms for dynamic expression evaluation and context-free recognition ⋮ A note on optimal parallel transformations of regular expressions to nondeterministic finite automata ⋮ Experiments with parallel branch-and-bound algorithms for the set covering problem

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A note on two problems in connexion with graphs
• Branch-and-bound and parallel computation: A historical note
• Constructing a perfect matching is in random NC
• The general problem solving algorithm and its implementation
• Towards a complexity theory of synchronous parallel computation
• The maximum flow problem is log space complete for P
• Reducibility by algebraic projections
• An observation on time-storage trade off
• Linear programming is log-space hard for P
• Dynamic programming and parallel computers
• Scheduling with Deadlines and Loss Functions
• Binary Trees and Parallel Scheduling Algorithms
• Anomalies in parallel branch-and-bound algorithms
• An Optimal Solution for the Channel-Assignment Problem
• A parallel algorithm for constructing minimum spanning trees
• Ultracomputers
• Parallel Matrix and Graph Algorithms
• Alternation
• A universal interconnection pattern for parallel computers
• Parallel Scheduling Algorithms
• Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems
• Bounds to Complexities of Networks for Sorting and for Switching
• Analysis Techniques for SIMD Machine Interconnection Networks and the Effects of Processor Address Masks
• The NP-completeness column: An ongoing guide
• Parallel Processing with the Perfect Shuffle

This page was built for publication: An introduction to parallelism in combinatorial optimization