On Lazy Bin Covering and packing problems

Mingen Lin; Yang; Jinhui Xu

doi:10.1007/11809678_36

On Lazy Bin Covering and packing problems

Mingen Lin
, Yang
, Jinhui Xu

Department of Computer Science and Engineering

SUNY Buffalo

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

5 Scopus citations

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 show its NP-hardness, then prove the approximation ratio of the First-Fit-Decreasing algorithm, and finally present an APTAS. For the online LBC problem, we give 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 [1]. For this problem, we prove that its offline version is no harder to approximate than the offline MRBP problem.

Original language	English
Title of host publication	Computing and Combinatorics - 12th Annual International Conference, COCOON 2006, Proceedings
Publisher	Springer Verlag
Pages	340-349
Number of pages	10
ISBN (Print)	3540369252, 9783540369257
DOIs	https://doi.org/10.1007/11809678_36
State	Published - 2006
Event	12th Annual International Conference on Computing and Combinatorics, COCOON 2006 - Taipei, Taiwan, Province of China Duration: Aug 15 2006 → Aug 18 2006

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	4112 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	12th Annual International Conference on Computing and Combinatorics, COCOON 2006
Country/Territory	Taiwan, Province of China
City	Taipei
Period	08/15/06 → 08/18/06

Access to Document

10.1007/11809678_36

Cite this

Lin, M., Yang, & Xu, J. (2006). On Lazy Bin Covering and packing problems. In Computing and Combinatorics - 12th Annual International Conference, COCOON 2006, Proceedings (pp. 340-349). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 4112 LNCS). Springer Verlag. https://doi.org/10.1007/11809678_36

@inproceedings{d47c8946da734e2cb96e49c95b8ad0fd,

title = "On Lazy Bin Covering and packing problems",

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 show its NP-hardness, then prove the approximation ratio of the First-Fit-Decreasing algorithm, and finally present an APTAS. For the online LBC problem, we give competitive analysis for the algorithms of Next-Fit, Worst-Fit, First-Fit, and a modified HARMONICM algorithm. The CCMRBP problem is a generalization of the Maximum Resource Bin Packing (MRBP) problem [1]. For this problem, we prove that its offline version is no harder to approximate than the offline MRBP problem.",

author = "Mingen Lin and Yang and Jinhui Xu",

year = "2006",

doi = "10.1007/11809678\_36",

language = "English",

isbn = "3540369252",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "340--349",

booktitle = "Computing and Combinatorics - 12th Annual International Conference, COCOON 2006, Proceedings",

address = "Germany",

note = "12th Annual International Conference on Computing and Combinatorics, COCOON 2006 ; Conference date: 15-08-2006 Through 18-08-2006",

}

Lin, M, Yang, & Xu, J 2006, On Lazy Bin Covering and packing problems. in Computing and Combinatorics - 12th Annual International Conference, COCOON 2006, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 4112 LNCS, Springer Verlag, pp. 340-349, 12th Annual International Conference on Computing and Combinatorics, COCOON 2006, Taipei, Taiwan, Province of China, 08/15/06. https://doi.org/10.1007/11809678_36

On Lazy Bin Covering and packing problems. / Lin, Mingen; Yang, ; Xu, Jinhui.
Computing and Combinatorics - 12th Annual International Conference, COCOON 2006, Proceedings. Springer Verlag, 2006. p. 340-349 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 4112 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - On Lazy Bin Covering and packing problems

AU - Lin, Mingen

AU - Yang,

AU - Xu, Jinhui

PY - 2006

Y1 - 2006

N2 - 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 show its NP-hardness, then prove the approximation ratio of the First-Fit-Decreasing algorithm, and finally present an APTAS. For the online LBC problem, we give competitive analysis for the algorithms of Next-Fit, Worst-Fit, First-Fit, and a modified HARMONICM algorithm. The CCMRBP problem is a generalization of the Maximum Resource Bin Packing (MRBP) problem [1]. For this problem, we prove that its offline version is no harder to approximate than the offline MRBP problem.

AB - 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 show its NP-hardness, then prove the approximation ratio of the First-Fit-Decreasing algorithm, and finally present an APTAS. For the online LBC problem, we give competitive analysis for the algorithms of Next-Fit, Worst-Fit, First-Fit, and a modified HARMONICM algorithm. The CCMRBP problem is a generalization of the Maximum Resource Bin Packing (MRBP) problem [1]. For this problem, we prove that its offline version is no harder to approximate than the offline MRBP problem.

UR - https://www.scopus.com/pages/publications/33749561909

U2 - 10.1007/11809678_36

DO - 10.1007/11809678_36

M3 - Conference contribution

AN - SCOPUS:33749561909

SN - 3540369252

SN - 9783540369257

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 340

EP - 349

BT - Computing and Combinatorics - 12th Annual International Conference, COCOON 2006, Proceedings

PB - Springer Verlag

T2 - 12th Annual International Conference on Computing and Combinatorics, COCOON 2006

Y2 - 15 August 2006 through 18 August 2006

ER -

On Lazy Bin Covering and packing problems

Abstract

Publication series

Conference

Access to Document

Other files and links

Fingerprint

Cite this