Improved approximation algorithms for maximum resource bin packing and Lazy Bin covering problems

Mingen Lin; Yang Yang; Jinhui Xu

doi:10.1007/11940128_57

Improved approximation algorithms for maximum resource bin packing and Lazy Bin covering problems

Mingen Lin
, Yang Yang
, Jinhui Xu

Department of Computer Science and Engineering

SUNY Buffalo

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

3 Scopus citations

Abstract

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 , achieved by the classical First-Fit-Increasing (FFI) algorithm [1]. In this paper, we give a new FFI-type algorithm with an approximation ratio of . For the offline LBC problem, it has been shown in [2] that the classical First-Fit-Decreasing (FFD) algorithm achieves an approximation ratio of . In this paper, we present a new FFD-type algorithm with an approximation ratio of . Both algorithms are simple, run in near linear time (i.e., O(n logn)), and therefore are practical.

Original language	English
Title of host publication	Algorithms and Computation - 17th International Symposium, ISAAC 2006, Proceedings
Pages	567-577
Number of pages	11
DOIs	https://doi.org/10.1007/11940128_57
State	Published - 2006
Event	17th International Symposium on Algorithms and Computation, ISAAC 2006 - Kolkata, India Duration: Dec 18 2006 → Dec 20 2006

Publication series

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

Conference

Conference	17th International Symposium on Algorithms and Computation, ISAAC 2006
Country/Territory	India
City	Kolkata
Period	12/18/06 → 12/20/06

Access to Document

10.1007/11940128_57

Cite this

Lin, M., Yang, Y., & Xu, J. (2006). Improved approximation algorithms for maximum resource bin packing and Lazy Bin covering problems. In Algorithms and Computation - 17th International Symposium, ISAAC 2006, Proceedings (pp. 567-577). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 4288 LNCS). https://doi.org/10.1007/11940128_57

Lin, Mingen ; Yang, Yang ; Xu, Jinhui. / Improved approximation algorithms for maximum resource bin packing and Lazy Bin covering problems. Algorithms and Computation - 17th International Symposium, ISAAC 2006, Proceedings. 2006. pp. 567-577 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{9a575284cb38433ea2868f58574032e7,

title = "Improved approximation algorithms for maximum resource bin packing and Lazy Bin covering problems",

abstract = "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 , achieved by the classical First-Fit-Increasing (FFI) algorithm [1]. In this paper, we give a new FFI-type algorithm with an approximation ratio of . For the offline LBC problem, it has been shown in [2] that the classical First-Fit-Decreasing (FFD) algorithm achieves an approximation ratio of . In this paper, we present a new FFD-type algorithm with an approximation ratio of . Both algorithms are simple, run in near linear time (i.e., O(n logn)), and therefore are practical.",

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

year = "2006",

doi = "10.1007/11940128\_57",

language = "English",

isbn = "3540496947",

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

pages = "567--577",

booktitle = "Algorithms and Computation - 17th International Symposium, ISAAC 2006, Proceedings",

note = "17th International Symposium on Algorithms and Computation, ISAAC 2006 ; Conference date: 18-12-2006 Through 20-12-2006",

}

Lin, M, Yang, Y & Xu, J 2006, Improved approximation algorithms for maximum resource bin packing and Lazy Bin covering problems. in Algorithms and Computation - 17th International Symposium, ISAAC 2006, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 4288 LNCS, pp. 567-577, 17th International Symposium on Algorithms and Computation, ISAAC 2006, Kolkata, India, 12/18/06. https://doi.org/10.1007/11940128_57

Improved approximation algorithms for maximum resource bin packing and Lazy Bin covering problems. / Lin, Mingen; Yang, Yang; Xu, Jinhui.
Algorithms and Computation - 17th International Symposium, ISAAC 2006, Proceedings. 2006. p. 567-577 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 4288 LNCS).

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

TY - GEN

T1 - Improved approximation algorithms for maximum resource bin packing and Lazy Bin covering problems

AU - Lin, Mingen

AU - Yang, Yang

AU - Xu, Jinhui

PY - 2006

Y1 - 2006

N2 - 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 , achieved by the classical First-Fit-Increasing (FFI) algorithm [1]. In this paper, we give a new FFI-type algorithm with an approximation ratio of . For the offline LBC problem, it has been shown in [2] that the classical First-Fit-Decreasing (FFD) algorithm achieves an approximation ratio of . In this paper, we present a new FFD-type algorithm with an approximation ratio of . Both algorithms are simple, run in near linear time (i.e., O(n logn)), and therefore are practical.

AB - 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 , achieved by the classical First-Fit-Increasing (FFI) algorithm [1]. In this paper, we give a new FFI-type algorithm with an approximation ratio of . For the offline LBC problem, it has been shown in [2] that the classical First-Fit-Decreasing (FFD) algorithm achieves an approximation ratio of . In this paper, we present a new FFD-type algorithm with an approximation ratio of . Both algorithms are simple, run in near linear time (i.e., O(n logn)), and therefore are practical.

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

U2 - 10.1007/11940128_57

DO - 10.1007/11940128_57

M3 - Conference contribution

AN - SCOPUS:77249172726

SN - 3540496947

SN - 9783540496946

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

SP - 567

EP - 577

BT - Algorithms and Computation - 17th International Symposium, ISAAC 2006, Proceedings

T2 - 17th International Symposium on Algorithms and Computation, ISAAC 2006

Y2 - 18 December 2006 through 20 December 2006

ER -

Lin M, Yang Y, Xu J. Improved approximation algorithms for maximum resource bin packing and Lazy Bin covering problems. In Algorithms and Computation - 17th International Symposium, ISAAC 2006, Proceedings. 2006. p. 567-577. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/11940128_57

Improved approximation algorithms for maximum resource bin packing and Lazy Bin covering problems

Abstract

Publication series

Conference

Access to Document

Other files and links

Fingerprint

Cite this