Improved Approximation Algorithms for Maximum Resource Bin Packing and Lazy Bin Covering Problems |
| |
Authors: | Mingen Lin Yang Yang Jinhui Xu |
| |
Affiliation: | 1. Department of Computer Science and Engineering, University at Buffalo, The State University of New York, Buffalo, NY, 14260, USA
|
| |
Abstract: | In this paper, we study two variants of the bin packing and covering problems called Maximum Resource Bin Packing (MRBP) and Lazy Bin Covering (LBC) problems, and present new approximation algorithms for them. For the offline MRBP problem, the previous best known approximation
ratio is
\frac65\frac{6}{5}
(=1.2) achieved by the classical First-Fit-Increasing (FFI) algorithm (Boyar et al. in Theor. Comput. Sci. 362(1–3):127–139, 2006). In this paper, we give a new FFI-type algorithm with an approximation ratio of
\frac8071\frac{80}{71}
(≈1.12676). For the offline LBC problem, it has been shown in Lin et al. (COCOON, pp. 340–349, 2006) that the classical First-Fit-Decreasing (FFD) algorithm achieves an approximation ratio of
\frac7160\frac{71}{60}
(≈1.18333). In this paper, we present a new FFD-type algorithm with an approximation ratio of
\frac1715\frac{17}{15}
(≈1.13333). Our algorithms are based on a pattern-based technique and a number of other observations. They run in near linear
time (i.e., O(nlog n)), and therefore are practical. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|