In Proc. 4th Conf. on Hypercubes, Concurrent Computers, and
Applications (1989), pp. 769-776.
Hypercube Algorithms for some NP-Hard Packing Problems
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.
Richard Fenrich, Russ Miller
Dept. of Computer Science, State University of New York at Buffalo
Quentin F. Stout
EECS Department, University of Michigan
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
Copyright © 2005-2016 Quentin F. Stout