DROPS

Document

APPROX

DOI: 10.4230/LIPIcs.APPROX/RANDOM.2020.52

Online Coloring of Short Intervals

Authors: Joanna Chybowska-Sokół, Grzegorz Gutowski, Konstanty Junosza-Szaniawski, Patryk Mikos, and Adam Polak

Published in: LIPIcs, Volume 176, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020)

Abstract

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, and proves that the problem we study can be strictly easier than online coloring of general 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, and that no algorithm beats the 5/2 asymptotic competitive ratio for all, arbitrarily large, values of σ. That last result shows that the problem we study can be strictly harder than unit interval coloring. Our main technical contribution is a recursive composition of strategies, which seems essential to prove any lower bound higher than 2.

Cite as

Joanna Chybowska-Sokół, Grzegorz Gutowski, Konstanty Junosza-Szaniawski, Patryk Mikos, and Adam Polak. Online Coloring of Short Intervals. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 176, pp. 52:1-52:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{chybowskasokol_et_al:LIPIcs.APPROX/RANDOM.2020.52,
  author =	{Chybowska-Sok\'{o}{\l}, Joanna and Gutowski, Grzegorz and Junosza-Szaniawski, Konstanty and Mikos, Patryk and Polak, Adam},
  title =	{{Online Coloring of Short Intervals}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020)},
  pages =	{52:1--52:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-164-1},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{176},
  editor =	{Byrka, Jaros{\l}aw and Meka, Raghu},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2020.52},
  URN =		{urn:nbn:de:0030-drops-126550},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2020.52},
  annote =	{Keywords: Online algorithms, graph coloring, interval graphs}
}

Search Results

Documents authored by Chybowska-Sokół, Joanna

Online Coloring of Short Intervals

Abstract

Cite as

Thanks for your feedback!

Could not send message