Online coloring of short intervals

2020
book section
conference proceedings
1
cris.lastimport.scopus2024-04-07T16:10:44Z
cris.lastimport.wos2024-04-10T01:35:35Z
dc.abstract.enWe study the online graph coloring problem restricted to the intersection graphs of intervals withlengths in[1,σ]. Forσ= 1it is the class of unit interval graphs, and forσ=∞the class of allinterval graphs. Our focus is on intermediary classes. We present a(1 +σ)-competitive algorithm,which beats the state of the art for1< σ <2, and proves that the problem we study can be strictlyeasier than online coloring of general interval graphs. On the lower bound side, we prove that noalgorithm is better than5/3-competitive for anyσ >1, nor better than7/4-competitive for anyσ >2, and that no algorithm beats the5/2asymptotic competitive ratio for all, arbitrarily large,values ofσ. That last result shows that the problem we study can be strictly harder than unitinterval coloring. Our main technical contribution is a recursive composition of strategies, whichseems essential to prove any lower bound higher than2.pl
dc.affiliationWydział Matematyki i Informatyki : Instytut Informatyki Analitycznejpl
dc.affiliationWydział Matematyki i Informatykipl
dc.conferenceApproximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2020pl
dc.conference.citySeattle
dc.conference.countryStany Zjednoczone
dc.conference.datefinish2020-08-19
dc.conference.datestart2020-08-17
dc.conference.shortcutRANDOM
dc.contributor.authorChybowska-Sokół, Joannapl
dc.contributor.authorGutowski, Grzegorz - 133968 pl
dc.contributor.authorJunosza-Szaniawski, Konstantypl
dc.contributor.authorMikos, Patryk - 201350 pl
dc.contributor.authorPolak, Adam - 177165 pl
dc.date.accessioned2020-10-30T16:06:45Z
dc.date.available2020-10-30T16:06:45Z
dc.date.issued2020pl
dc.date.openaccess0
dc.description.accesstimew momencie opublikowania
dc.description.conftypeinternationalpl
dc.description.physical52:1–52:18pl
dc.description.publication7pl
dc.description.seriesLeibniz International Proceedings in Informatics (LIPIcs)
dc.description.seriesnumber176
dc.description.versionostateczna wersja wydawcy
dc.identifier.doi10.4230/LIPIcs.APPROX/RANDOM.2020.52pl
dc.identifier.isbn978-3-95977-164-1pl
dc.identifier.project2016/21/B/ST6/02165pl
dc.identifier.project2014/14/A/ST6/00138pl
dc.identifier.projectDI2012 018942pl
dc.identifier.project2016/23/N/ST1/03181pl
dc.identifier.projectROD UJ / OPpl
dc.identifier.seriesissn1868-8969
dc.identifier.urihttps://ruj.uj.edu.pl/xmlui/handle/item/251952
dc.languageengpl
dc.language.containerengpl
dc.pbn.affiliationDziedzina nauk ścisłych i przyrodniczych : informatykapl
dc.pubinfoDagstuhl : Schloss Dagstuhl-Leibniz-Zentrum fuer Informatikpl
dc.rightsUdzielam licencji. Uznanie autorstwa 3.0 Polska*
dc.rights.licenceCC-BY
dc.rights.urihttp://creativecommons.org/licenses/by/3.0/legalcode*
dc.share.typeotwarte repozytorium
dc.subject.enonline algorithmspl
dc.subject.engraph coloringpl
dc.subject.eninterval graphspl
dc.subtypeConferenceProceedingspl
dc.titleOnline coloring of short intervalspl
dc.title.containerApproximation, randomization, and combinatorial optimization : algorithms and techniques (APPROX/RANDOM 2020)pl
dc.typeBookSectionpl
dspace.entity.typePublication
Affiliations

* The migration of download and view statistics prior to the date of April 8, 2024 is in progress.

Views
0
Views per month
Downloads
gutowski_et-al_online_coloring_of_short_intervals_2020.pdf
1