Improved Approximation Algorithms for Maximum Resource Bin Packing and Lazy Bin Covering Problems

摘要

In this paper, we study two variants of the bin packing /covering problems called Maximum Resource Bin Packing (MRBP) and Lazy Bin Covering (LBC) problems, and present new approximation algorithms for each of them. For the offline MRBP problem, the previous best known approximation ratio is 6/5 = 1.2, achieved by the classical First-Fit-Increasing (FFI) algorithm. In this paper, we give a new FFI-type algorithm with an approximation ratio of 80/71 ≈ 1.12676. For the offline LBC problem, it has been shown in that the classical First-Fit-Decreasing (FFD) algorithm achieves an approximation ratio of 71/60 ≈ 1.18333. In this paper, we present a new FFD-type algorithm with an approximation ratio of 17/15 ≈ 1.13333. Both algorithms are simple, run in near linear time (i.e., O(n log n)), and therefore are practical.