Online Coloring of Short Intervals
share
We study the online graph coloring problem restricted to the intersection graphs of intervals with lengths in [1,σ]. For σ=1 it is the class of unit interval graphs, and for σ=∞ the class of all interval graphs. Our focus is on intermediary classes. We present a (1+σ)-competitive algorithm, which beats the state of the art for 1 < σ < 2. For σ = 1 our algorithm matches the performance of FirstFit, which is 2-competitive for unit interval graphs. For σ=2 it matches the Kierstead-Trotter algorithm, which is 3-competitive for all interval graphs. On the lower bound side, we prove that no algorithm is better than 5/3-competitive for any σ>1, nor better than 7/4-competitive for any σ>2, nor better than 5/2-competitive for arbitrarily large values of σ.
READ FULL TEXT