PROBABILISTIC ANALYSIS AND PARALLELIZATION OF BIN-PACKING ALGORITHMS

Abstract

Bin-packing problems appear in many applications. Since the general form of bin-packing problems is NP-hard, emphasis is placed on the study of heuristic algorithms. To compare the performance of heuristic algorithms, their average-case performance is an appropriate measure when the input of these algorithms are drawn from some known distributions. In this thesis, we propose a heuristic algorithm, HashPacking. Based on this algorithm, we formulate algorithms for various settings and study their average-case performance. Furthermore, we give an expected work optimal parallel algorithm based on HashPacking for one dimensional bin-packing. To obtain this optimal parallel algorithm, we develop a randomized version of Brent's Scheduling Principle, which under certain conditions, is able to transform a parallel algorithm to an expected work optimal randomized parallel algorithm.