Name
Abstract | ||
|---|---|---|
In this paper, we study two interesting variants of the classical bin packing problem, called Lazy Bin Covering (LBC) and Cardinality Constrained Maximum Resource Bin Packing (CCMRBP) problems. For the offline LBC problem, we first prove the approximation ratio of the First-Fit-Decreasing and First-Fit-Increasing algorithms, then present an APTAS. For the online LBC problem, we give a competitive analysis for the algorithms of Next-Fit, Worst-Fit, First-Fit, and a modified HARMONIC"M algorithm. The CCMRBP problem is a generalization of the Maximum Resource Bin Packing (MRBP) problem Boyar et al. (2006) [1]. For this problem, we prove that its offline version is no harder to approximate than the offline MRBP problem. |
Year | DOI | Venue |
|---|---|---|
2010 | 10.1016/j.tcs.2009.10.006 | Theor. Comput. Sci. |
Keywords | Field | DocType |
cardinality constrained maximum resource,packing problem,maximum resource bin packing,offline version,approximation algorithms,lazy bin covering,offline mrbp problem,ccmrbp problem,classical bin packing problem,offline lbc problem,online lbc problem,bin packing,bin packing problem,competitive analysis | Resource management,Discrete mathematics,Combinatorics,Bin,Packing problems,Computer science,Cardinal number,Cardinality,Bin packing problem,Competitive analysis | Journal |
Volume | Issue | ISSN |
411 | 1 | Theoretical Computer Science |
ISBN | Citations | PageRank |
3-540-36925-2 | 5 | 0.55 |
References | Authors | |
15 | 3 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Mingen Lin | 1 | 66 | 4.27 |
| Yang Yang | 2 | 259 | 18.33 |
| Jinhui Xu | 3 | 665 | 78.86 |