Simple view
Full metadata view
Authors
Statistics
Online coloring of short intervals
online algorithms
graph coloring
interval graphs
We 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.
cris.lastimport.scopus | 2024-04-07T16:10:44Z | |
cris.lastimport.wos | 2024-04-10T01:35:35Z | |
dc.abstract.en | We 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.affiliation | Wydział Matematyki i Informatyki : Instytut Informatyki Analitycznej | pl |
dc.affiliation | Wydział Matematyki i Informatyki | pl |
dc.conference | Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2020 | pl |
dc.conference.city | Seattle | |
dc.conference.country | Stany Zjednoczone | |
dc.conference.datefinish | 2020-08-19 | |
dc.conference.datestart | 2020-08-17 | |
dc.conference.shortcut | RANDOM | |
dc.contributor.author | Chybowska-Sokół, Joanna | pl |
dc.contributor.author | Gutowski, Grzegorz - 133968 | pl |
dc.contributor.author | Junosza-Szaniawski, Konstanty | pl |
dc.contributor.author | Mikos, Patryk - 201350 | pl |
dc.contributor.author | Polak, Adam - 177165 | pl |
dc.date.accessioned | 2020-10-30T16:06:45Z | |
dc.date.available | 2020-10-30T16:06:45Z | |
dc.date.issued | 2020 | pl |
dc.date.openaccess | 0 | |
dc.description.accesstime | w momencie opublikowania | |
dc.description.conftype | international | pl |
dc.description.physical | 52:1–52:18 | pl |
dc.description.publication | 7 | pl |
dc.description.series | Leibniz International Proceedings in Informatics (LIPIcs) | |
dc.description.seriesnumber | 176 | |
dc.description.version | ostateczna wersja wydawcy | |
dc.identifier.doi | 10.4230/LIPIcs.APPROX/RANDOM.2020.52 | pl |
dc.identifier.isbn | 978-3-95977-164-1 | pl |
dc.identifier.project | 2016/21/B/ST6/02165 | pl |
dc.identifier.project | 2014/14/A/ST6/00138 | pl |
dc.identifier.project | DI2012 018942 | pl |
dc.identifier.project | 2016/23/N/ST1/03181 | pl |
dc.identifier.project | ROD UJ / OP | pl |
dc.identifier.seriesissn | 1868-8969 | |
dc.identifier.uri | https://ruj.uj.edu.pl/xmlui/handle/item/251952 | |
dc.language | eng | pl |
dc.language.container | eng | pl |
dc.pbn.affiliation | Dziedzina nauk ścisłych i przyrodniczych : informatyka | pl |
dc.pubinfo | Dagstuhl : Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik | pl |
dc.rights | Udzielam licencji. Uznanie autorstwa 3.0 Polska | * |
dc.rights.licence | CC-BY | |
dc.rights.uri | http://creativecommons.org/licenses/by/3.0/legalcode | * |
dc.share.type | otwarte repozytorium | |
dc.subject.en | online algorithms | pl |
dc.subject.en | graph coloring | pl |
dc.subject.en | interval graphs | pl |
dc.subtype | ConferenceProceedings | pl |
dc.title | Online coloring of short intervals | pl |
dc.title.container | Approximation, randomization, and combinatorial optimization : algorithms and techniques (APPROX/RANDOM 2020) | pl |
dc.type | BookSection | pl |
dspace.entity.type | Publication |
* The migration of download and view statistics prior to the date of April 8, 2024 is in progress.
Views
0
Views per month
Downloads
Open Access