BIB-VERSION:: CS-TR-v2.0
          ID:: STAN//CS-TR-88-1200
       ENTRY:: April 24, 1995
ORGANIZATION:: Stanford University, Department of Computer Science
       TITLE:: Parallel Approximation Algorithms for Bin Packing
        TYPE:: Technical Report
      AUTHOR:: Anderson, R. J.
      AUTHOR:: Mayr, E. W.
      AUTHOR:: Warmuth, M. K.
        DATE:: March 1988
       PAGES:: 18
    ABSTRACT:: We study the parallel complexity of polynomial heuristics for
               the bin packing problem. We show that some well-known (and
               simple) moethods like first-fit- decreasing are P-complete,
               and it is hence very unlikely that they can be efficiently
               parallelized. On the other hand, we exhibit an optimal NC
               algorithm that achieves the same performance bound as does
               FFD. Finally, we discuss parallelization of polynomial
               approximation algorithms for bin packing based on
               discretization.
       NOTES:: [Adminitrivia V1/Prg/19950424]
         END:: STAN//CS-TR-88-1200