Hypercube Algorithms for some NP-Hard Problems

In Proc. 4th Conf. on Hypercubes, Concurrent Computers, and Applications (1989), pp. 769-776.

Hypercube Algorithms for some NP-Hard Packing Problems

Richard Fenrich, Russ Miller
Dept. of Computer Science, State University of New York at Buffalo

Quentin F. Stout
EECS Department, University of Michigan

Abstract: This research is concerned with approximation algorithms for NP-hard optimization problems on hypercube multiprocessors. We investigate methods of solving such problems, focusing on the tradeoffs in running time, number of active nodes, input size, and accuracy of solution. In this paper, we concentrate on approximation algorithms for the 2-dimensional bin packing problem, i.e., the problem of producing a nonoverlapping packing of a set of rectangles within a vertical strip of fixed width that will minimize the height of the strip. Results are given for level algorithms incorporating next fit, best fit, and first fit level filling strategies. We have also evaluated several heuristic level unpacking and level combining strategies, and discuss how these modifications affect the performance of the basic algorithms. The results were obtained on a 32 node Intel iPSC/2.

Keywords: 2-dimensional bin packing, best fit, NP-hard, parallel computing, hypercube computer, level algorithms

Other papers in parallel computing
Overview of work on parallel computing