Research On Approximation Algorithms For Online Bin Packing Problems

The bin packing problem is one of the oldest problems in computer science. Since it has been studied over forty years, many critical results have been published. Some theories, such as the idea of proving lower bounds and competitive analysis on the performance of online algorithm, originate from the study of this problem. Bin packing problem has been widely used in many real world applications such as multiprocessor scheduling in computer science and task scheduling and loading trucks in industry.Recently, a lot of researches turn to study the bounded space online bin packing with bounded space smaller than three and online bin packing with advice problem. Till now, the best upper bound of 2-bounded space online two-dimensional bin packing problem is 3.8, proposed by Januszewski by using the idea of bricks, and the best result of online one-dimensional bin packing with advice is 4/3 by Boyar et al. In this paper we improved both of the two results and extended the method to higher-dimensional packing problem. Generally speaking, our work is as follows:1. For the 2-bounded space online square packing problem, this paper designed an improved bricks partitioning scheme. We dissect the hybrid bin into a new type of bricks and pack some small items together with big items into the hybrid bin to fill in the empty space. In this way, the occupancy of both two types of open bins is improved. Through analysis, the improved upper bound 3.63556 is obtained.2. The method of 2-bounded square packing can be extended to 2-bounded space cube packing and high-dimenional hypercube packing. Through dissecting both dimensional of each open bin, a 5.43 and a 32/21·2d-competitive ratio online algorithm is presented for cube packing and hypercube packing seperately. Both two results are the first studies of the corresponding problems.3. Inspired by Boyar et al’s work of competitive ratio 4/3 with two advice bits per item, we show that if the oracle provides three bits of advice per item, applying an item classification scheme different from Boyar et al’s, we can obtain an online algorithm with competitive ratio 5/4 to pack the item list. Furthermore, we show that our algorithm can retain the same competitive ratio 5/4 with only two bits of advice per item, hence improving the known result. For the lower bound, we prove that for any online algorithm with advice to achieve optimal packing, at least (n-3OPT) log OPT bits of advice in total is needed.4. Extending the method to two-dimensional square and rectangular packing, this paper proposes a 2 and a 2.25-competitive ratio online algorithm for two-dimenional square and rectangular packing with three bits of advice seperately. These are the first studies of two-dimensional online packing with advice.5. At last, this paper focus on the parallelization of two-dimensional square packing problem. A 9/4-worst case asymptotic error bound algorithm with time complexity θ(n) is showed. However the upper bound of our parallel algorithm is a little worse than Han’s algorithm, the analysis of our algorithm is more simple and the time complexity is improved.