LIPIcs.APPROX-RANDOM.2020.52.pdf
- Filesize: 0.64 MB
- 18 pages
Document
Online Coloring of Short Intervals
Authors
Joanna Chybowska-Sokół 
,
Grzegorz Gutowski ,
Konstanty Junosza-Szaniawski ,
Patryk Mikos ,
Adam Polak
-
Part of:
Volume:
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: International Conference on Randomization and Computation (RANDOM)
Conference: International Conference on Approximation Algorithms for Combinatorial Optimization Problems (APPROX) - License:
Creative Commons Attribution 3.0 Unported license
- Publication Date: 2020-08-11
File
Document Identifiers
Author Details
- Faculty of Mathematics and Information Science, Warsaw University of Technology, Poland
- Institute of Theoretical Computer Science, Faculty of Mathematics and Computer Science, Jagiellonian University, Kraków, Poland
- Faculty of Mathematics and Information Science, Warsaw University of Technology, Poland
- Institute of Theoretical Computer Science, Faculty of Mathematics and Computer Science, Jagiellonian University, Kraków, Poland
Cite AsGet BibTex
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)
https://doi.org/10.4230/LIPIcs.APPROX/RANDOM.2020.52
https://doi.org/10.4230/LIPIcs.APPROX/RANDOM.2020.52
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.
Subject Classification
ACM Subject Classification
- Theory of computation → Online algorithms
Keywords
- Online algorithms
- graph coloring
- interval graphs
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
- Yossi Azar, Amos Fiat, Meital Levy, and N.S. Narayanaswamy. An improved algorithm for online coloring of intervals with bandwidth. Theoretical Computer Science, 363(1):18-27, 2006. URL: https://doi.org/10.1016/j.tcs.2006.06.014.
- Seymour Benzer. On the topology of the genetic fine structure. Proceedings of the National Academy of Sciences of the United States of America, 45(11):1607-1620, 1959. URL: https://doi.org/10.1073/pnas.45.11.1607.
- Marek Chrobak and Maciej Ślusarek. On some packing problem related to dynamic storage allocation. RAIRO, Theoretical Informatics and Applications, 22(4):487-499, 1988. URL: http://www.numdam.org/item/ITA_1988__22_4_487_0.
- Leah Epstein and Meital Levy. Online interval coloring and variants. In ICALP 2005: 32nd International Colloquim on Automata, Languages and Programming, Lisbon, Portugal, July 2005. Proceedings, volume 3580 of Lecture Notes in Computer Science, pages 602-613, 2005. URL: https://doi.org/10.1007/11523468_49.
- P. C. Fishburn and R. L. Graham. Classes of interval graphs under expanding length restrictions. Journal of Graph Theory, 9(4):459-472, 1985. URL: https://doi.org/10.1002/jgt.3190090405.
-
Martin Charles Golumbic. Algorithmic Graph Theory and Perfect Graphs (Annals of Discrete Mathematics, Vol 57). Elsevier, 2 edition, 2004.
- Magnús M. Halldórsson. Parallel and on-line graph coloring. Journal of Algorithms, 23(2):265-280, 1997. URL: https://doi.org/10.1006/jagm.1996.0836.
- Magnús M. Halldórsson and Mario Szegedy. Lower bounds for on-line graph coloring. Theoretical Computer Science, 130(1):163-174, 1994. URL: https://doi.org/10.1016/0304-3975(94)90157-0.
- Konstanty Junosza-Szaniawski, Paweł Rzążewski, Joanna Sokół, and Krzysztof Węsek. Online coloring and L(2,1)-labeling of unit disk intersection graphs. SIAM Journal on Discrete Mathematics, 32(2):1335-1350, 2018. URL: https://doi.org/10.1137/16M1097821.
- Henry A. Kierstead, David A. Smith, and William T. Trotter. First-fit coloring on interval graphs has performance ratio at least 5. European Journal of Combinatorics, 51:236-254, 2016. URL: https://doi.org/10.1016/j.ejc.2015.05.015.
- Henry A. Kierstead and William T. Trotter. An extremal problem in recursive combinatorics. In 12th Southeastern Conference on Combinatorics, Graph Theory and Computing, Baton Rouge, LA, USA, March 1981. Proceedings, vol. II, volume 33 of Congressus Numerantium, pages 143-153, 1981. URL: https://people.math.gatech.edu/~trotter/papers/29.pdf.
- C. Lekkeikerker and J. Boland. Representation of a finite graph by a set of intervals on the real line. Fundamenta Mathematicae, 51(1):45-64, 1962. URL: http://eudml.org/doc/213681.
- N. S. Narayanaswamy and R. Subhash Babu. A note on first-fit coloring of interval graphs. Order, 25(1):49-53, 2008. URL: https://doi.org/10.1007/s11083-008-9076-6.
- Maciej Ślusarek. A coloring algorithm for interval graphs. In MFCS 1989: Symposium on Mathematical Foundations of Computer Science, Porąbka-Kozubnik, Poland, August 1989. Proceedings, volume 379 of Lecture Notes in Computer Science, pages 471-480, 1989. URL: https://doi.org/10.1007/3-540-51486-4_93.