MANIP—A Multicomputer Architecture for Solving Combinatonal Extremum-Search Problems
- 1 May 1984
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Computers
- Vol. C-33 (5) , 377-390
- https://doi.org/10.1109/tc.1984.1676453
Abstract
In this paper, we propose and analyze the design of MANIP, a parallel machine for processing nondeterministic polynomial (NP)-hard problems. The most general technique that can be used to solve a wide variety of NP-hard problems on a uniprocessor system, optimally or suboptimally, is the branch-and-bound algorithm. We have adapted and extended branch-and-bound algorithms for parallel processing. The parallel branch-and-bound algorithmn requires a combination of sorting and merging that will be too inefficient to perform in a common memory. We have proposed a system with distributed intelligence so that sorting can be carried out efticiently. A unidirectional ring network is shown to be the most cost-effective interprocessor communication network. The performance on the proposed system is evaluated using the vertex-covering problem.Keywords
This publication has 17 references indexed in Scilit:
- Anomalies in parallel branch-and-bound algorithmsCommunications of the ACM, 1984
- Random Trees and the Analysis of Branch and Bound ProceduresJournal of the ACM, 1984
- Parallel Search of Strongly Ordered Game TreesACM Computing Surveys, 1982
- On Parallel Computation for the Knapsack ProblemJournal of the ACM, 1982
- Bounds on Selection NetworksSIAM Journal on Computing, 1980
- A Patching Algorithm for the Nonsymmetric Traveling-Salesman ProblemSIAM Journal on Computing, 1979
- General Techniques for Combinatorial ApproximationOperations Research, 1977
- Parallelism in Comparison ProblemsSIAM Journal on Computing, 1975
- Sorting algorithms with minimum memoryCybernetics and Systems Analysis, 1969
- Branch-and-Bound Methods: A SurveyOperations Research, 1966