Almost optimal solutions for bin coloring problems

Mingen Lin; Zhiyong Lin; Jinhui Xu

doi:10.1007/11602613_10

Almost optimal solutions for bin coloring problems

Mingen Lin
, Zhiyong Lin
, Jinhui Xu

Department of Computer Science and Engineering

SUNY Buffalo

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

2 Scopus citations

Abstract

In this paper we study two interesting bin coloring problems: Minimum Bin Coloring Problem (MinBC) and Online Maximum Bin Coloring Problem (OMaxBC), motivated from several applications in networking. For the MinBC problem, we first show that it is NP-complete, and then present two near linear time approximation algorithms to achieve almost optimal solutions, i.e., no more than OPT + 2 and OPT + 1 respectively, where OPT is the optimal solution. For the OMaxBC problem, we first introduce a deterministic 2-competitive greedy algorithm, and then give lower bounds for any deterministic and randomized (against adaptive offline adversary) online algorithms. The lower bounds show that our deterministic algorithm achieves the best possible competitive ratio.

Original language	English
Title of host publication	Algorithms and Computation - 16th International Symposium, ISAAC 2005, Proceedings
Publisher	Springer Verlag
Pages	82-91
Number of pages	10
ISBN (Print)	3540309357, 9783540309352
DOIs	https://doi.org/10.1007/11602613_10
State	Published - 2005
Event	16th International Symposium on Algorithms and Computation, ISAAC 2005 - Hainan, China Duration: Dec 19 2005 → Dec 21 2005

Publication series

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

Conference

Conference	16th International Symposium on Algorithms and Computation, ISAAC 2005
Country/Territory	China
City	Hainan
Period	12/19/05 → 12/21/05

Access to Document

10.1007/11602613_10

Cite this

Lin, M., Lin, Z., & Xu, J. (2005). Almost optimal solutions for bin coloring problems. In Algorithms and Computation - 16th International Symposium, ISAAC 2005, Proceedings (pp. 82-91). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 3827 LNCS). Springer Verlag. https://doi.org/10.1007/11602613_10

@inproceedings{4f918756bc5f4e26981ad2d5278bf3f4,

title = "Almost optimal solutions for bin coloring problems",

abstract = "In this paper we study two interesting bin coloring problems: Minimum Bin Coloring Problem (MinBC) and Online Maximum Bin Coloring Problem (OMaxBC), motivated from several applications in networking. For the MinBC problem, we first show that it is NP-complete, and then present two near linear time approximation algorithms to achieve almost optimal solutions, i.e., no more than OPT + 2 and OPT + 1 respectively, where OPT is the optimal solution. For the OMaxBC problem, we first introduce a deterministic 2-competitive greedy algorithm, and then give lower bounds for any deterministic and randomized (against adaptive offline adversary) online algorithms. The lower bounds show that our deterministic algorithm achieves the best possible competitive ratio.",

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

year = "2005",

doi = "10.1007/11602613\_10",

language = "English",

isbn = "3540309357",

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

publisher = "Springer Verlag",

pages = "82--91",

booktitle = "Algorithms and Computation - 16th International Symposium, ISAAC 2005, Proceedings",

address = "Germany",

note = "16th International Symposium on Algorithms and Computation, ISAAC 2005 ; Conference date: 19-12-2005 Through 21-12-2005",

}

Lin, M, Lin, Z & Xu, J 2005, Almost optimal solutions for bin coloring problems. in Algorithms and Computation - 16th International Symposium, ISAAC 2005, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 3827 LNCS, Springer Verlag, pp. 82-91, 16th International Symposium on Algorithms and Computation, ISAAC 2005, Hainan, China, 12/19/05. https://doi.org/10.1007/11602613_10

Almost optimal solutions for bin coloring problems. / Lin, Mingen; Lin, Zhiyong; Xu, Jinhui.
Algorithms and Computation - 16th International Symposium, ISAAC 2005, Proceedings. Springer Verlag, 2005. p. 82-91 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 3827 LNCS).

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

TY - GEN

T1 - Almost optimal solutions for bin coloring problems

AU - Lin, Mingen

AU - Lin, Zhiyong

AU - Xu, Jinhui

PY - 2005

Y1 - 2005

N2 - In this paper we study two interesting bin coloring problems: Minimum Bin Coloring Problem (MinBC) and Online Maximum Bin Coloring Problem (OMaxBC), motivated from several applications in networking. For the MinBC problem, we first show that it is NP-complete, and then present two near linear time approximation algorithms to achieve almost optimal solutions, i.e., no more than OPT + 2 and OPT + 1 respectively, where OPT is the optimal solution. For the OMaxBC problem, we first introduce a deterministic 2-competitive greedy algorithm, and then give lower bounds for any deterministic and randomized (against adaptive offline adversary) online algorithms. The lower bounds show that our deterministic algorithm achieves the best possible competitive ratio.

AB - In this paper we study two interesting bin coloring problems: Minimum Bin Coloring Problem (MinBC) and Online Maximum Bin Coloring Problem (OMaxBC), motivated from several applications in networking. For the MinBC problem, we first show that it is NP-complete, and then present two near linear time approximation algorithms to achieve almost optimal solutions, i.e., no more than OPT + 2 and OPT + 1 respectively, where OPT is the optimal solution. For the OMaxBC problem, we first introduce a deterministic 2-competitive greedy algorithm, and then give lower bounds for any deterministic and randomized (against adaptive offline adversary) online algorithms. The lower bounds show that our deterministic algorithm achieves the best possible competitive ratio.

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

U2 - 10.1007/11602613_10

DO - 10.1007/11602613_10

M3 - Conference contribution

AN - SCOPUS:33744965436

SN - 3540309357

SN - 9783540309352

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

SP - 82

EP - 91

BT - Algorithms and Computation - 16th International Symposium, ISAAC 2005, Proceedings

PB - Springer Verlag

T2 - 16th International Symposium on Algorithms and Computation, ISAAC 2005

Y2 - 19 December 2005 through 21 December 2005

ER -

Almost optimal solutions for bin coloring problems

Abstract

Publication series

Conference

Access to Document

Other files and links

Fingerprint

Cite this