A Parallel Implementation of the Column Subtraction Algorithm

Abstract

We have implemented Harche and Thompson's column subtraction algorithm for the set partitioning problem on the CN-200 Connection Machine. The implementation involved partitioning the large array of processors in the CM-2 into segments and letting each segment explore a different part of the search tree generated by the column subtraction algorithm. Our reported computational results indicate that the segments are highly utilized and that good speedups are obtained as the number of segments is increased. Parallel processing, Branch-and-Bound method, Column subtraction, Set partitioning.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Dec 22, 1993
Accession Number
ADA275922

Entities

People

  • T. H. Smith

Organizations

  • Carnegie Mellon University

Tags

Communities of Interest

  • Energy and Power Technologies

DTIC Thesaurus Topics

  • Algorithms
  • Computations
  • Computer Programming
  • Computer Science
  • Computers
  • Computing-Related Activities
  • Contracts
  • Language
  • Linear Programming
  • Mathematics
  • Military Research
  • Parallel Computing
  • Parallel Processing
  • Schools
  • South Africa
  • Trees (Data Structures)
  • Universities

Readers

  • Operations Research
  • Parallel and Distributed Computing.
  • Speech Processing/Speech Recognition.