Online interval coloring with packing constraints

被引：2

作者：

Epstein, Leah ^{[1
]}

Levy, Meital ^{[2
]}

机构：

[1] Univ Haifa, Dept Math, IL-31905 Haifa, Israel

[2] Tel Aviv Univ, Sch Comp Sci, Tel Aviv, Israel

来源：

THEORETICAL COMPUTER SCIENCE | 2008年 / 407卷 / 1-3期

关键词：

Interval coloring; Bin packing; Online algorithms;

D O I：

10.1016/j.tcs.2008.05.018

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

We study online interval coloring problems with bandwidth. We are interested in some variants motivated by bin packing problems. Specifically we consider open-end coloring, cardinality constrained coloring, coloring with vector constraints and finally a combination of both the cardinality and the vector constraints. We construct competitive algorithms for each of the variants. Additionally, we present a lower bound of 24/7 for interval coloring with bandwidth, which holds for all the above models, and improves the current lower bound for the standard interval coloring with bandwidth problem. (C) 2008 Elsevier B.V. All rights reserved.

引用

页码：203 / 212

页数：10

共 23 条

[1]

Adamy U, 2004, LECT NOTES COMPUT SC, V2909, P1

[2] Tradeoffs in worst-case equilibria [J].

Awerbuch, Baruch ;

Azar, Yossi ;

Richter, Yossi ;

Tsur, Dekel .

THEORETICAL COMPUTER SCIENCE, 2006, 361 (2-3) :200-209

[3] Algorithms for on-line bin-packing problems with cardinality constraints [J].

Babel, L ;

Chen, B ;

Kellerer, H ;

Kotov, V .

DISCRETE APPLIED MATHEMATICS, 2004, 143 (1-3) :238-251

[4]

BLITZ D, 1996, LOWER BOUNDS A UNPUB

[5] Approximation schemes for ordered vector packing problems [J].

Caprara, A ;

Kellerer, H ;

Pferschy, U .

NAVAL RESEARCH LOGISTICS, 2003, 50 (01) :58-69

[6] ON SOME PACKING PROBLEM RELATED TO DYNAMIC STORAGE-ALLOCATION [J].

CHROBAK, M ;

SLUSAREK, M .

RAIRO-INFORMATIQUE THEORIQUE ET APPLICATIONS-THEORETICAL INFORMATICS AND APPLICATIONS, 1988, 22 (04) :487-499

[7]

Csirik J, 1998, LECT NOTES COMPUT SC, V1442, P147, DOI 10.1007/BFb0029568

[8]

EPSTEIN L, 2005, P 32 INT C AUT LANG, P602

[9] Online bin packing with cardinality constraints [J].

Epstein, Leah .

SIAM JOURNAL ON DISCRETE MATHEMATICS, 2006, 20 (04) :1015-1030

[10]

GALAMBOS G, 1994, ACTA CYBERNET, V10, P23

← 1 2 3 →