Recoloring interval graphs with limited recourse budget

2020
book section
conference proceedings
cris.lastimport.wos2024-04-09T20:20:38Z
dc.abstract.enWe consider the problem of coloring an interval graph dynamically. Intervals arrive one after the other and have to be colored immediately such that no two intervals of the same color overlap. In each step only a limited number of intervals may be recolored to maintain a proper coloring (thus interpolating between the well-studied online and offline settings). The number of allowed recolorings per step is the so-called recourse budget. Our main aim is to prove both upper and lower bounds on the required recourse budget for interval graphs, given a bound on the allowed number of colors. For general interval graphs with n vertices and chromatic number k it is known that some recoloring is needed even if we have 2k colors available. We give an algorithm that maintains a 2k-coloring with an amortized recourse budget of $𝒪(log n)$. For maintaining a k-coloring with k ≤ n, we give an amortized upper bound of 𝒪(k⋅ k! ⋅ √n), and a lower bound of $Ω(k) for k ∈ 𝒪(√n)$, which can be as large as $Ω(√n$). For unit interval graphs it is known that some recoloring is needed even if we have k+1 colors available. We give an algorithm that maintains a (k+1)-coloring with at most $𝒪(k²)$ recolorings per step in the worst case. We also give a lower bound of $Ω(log n)$ on the amortized recourse budget needed to maintain a k-coloring. Additionally, for general interval graphs we show that if one does not insist on maintaining an explicit coloring, one can have a k-coloring algorithm which does not incur a factor of $𝒪(k ⋅ k! ⋅ √n)$ in the running time. For this we provide a data structure, which allows for adding intervals in $𝒪(k² log³ n)$ amortized time per update and querying for the color of a particular interval in $𝒪(log n) time$. Between any two updates, the data structure answers consistently with some optimal coloring. The data structure maintains the coloring implicitly, so the notion of recourse budget does not apply to it.pl
dc.affiliationWydział Matematyki i Informatyki : Instytut Informatyki Analitycznejpl
dc.conference17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020)pl
dc.conference.cityTórshavn
dc.conference.countryFaroe Islands
dc.conference.datefinish2020-07-24
dc.conference.datestart2020-07-22
dc.contributor.authorBosek, Bartłomiej - 114402 pl
dc.contributor.authorDisser, Yannpl
dc.contributor.authorFeldmann, Andreas Emilpl
dc.contributor.authorPawlewicz, Jakubpl
dc.contributor.authorZych-Pawlewicz, Annapl
dc.date.accessioned2020-11-07T18:00:12Z
dc.date.available2020-11-07T18:00:12Z
dc.date.issued2020pl
dc.date.openaccess0
dc.description.accesstimew momencie opublikowania
dc.description.conftypeinternationalpl
dc.description.physical17:1-17:23pl
dc.description.publication0,9pl
dc.description.seriesLeibniz International Proceedings in Informatics (LIPIcs)
dc.description.seriesnumber162
dc.description.versionostateczna wersja wydawcy
dc.identifier.doi10.4230/LIPIcs.SWAT.2020.17pl
dc.identifier.isbn978-3-95977-150-4pl
dc.identifier.project2017/26/D/ST6/00264pl
dc.identifier.project2017/26/D/ST6/00264pl
dc.identifier.projectROD UJ / OPpl
dc.identifier.seriesissn1868-8969
dc.identifier.urihttps://ruj.uj.edu.pl/xmlui/handle/item/252948
dc.languageengpl
dc.language.containerengpl
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.subtypeConferenceProceedingspl
dc.titleRecoloring interval graphs with limited recourse budgetpl
dc.title.container17th Scandinavian symposium and workshops on algorithm theory (SWAT 2020)pl
dc.typeBookSectionpl
dspace.entity.typePublication
cris.lastimport.wos
2024-04-09T20:20:38Z
dc.abstract.enpl
We consider the problem of coloring an interval graph dynamically. Intervals arrive one after the other and have to be colored immediately such that no two intervals of the same color overlap. In each step only a limited number of intervals may be recolored to maintain a proper coloring (thus interpolating between the well-studied online and offline settings). The number of allowed recolorings per step is the so-called recourse budget. Our main aim is to prove both upper and lower bounds on the required recourse budget for interval graphs, given a bound on the allowed number of colors. For general interval graphs with n vertices and chromatic number k it is known that some recoloring is needed even if we have 2k colors available. We give an algorithm that maintains a 2k-coloring with an amortized recourse budget of $𝒪(log n)$. For maintaining a k-coloring with k ≤ n, we give an amortized upper bound of 𝒪(k⋅ k! ⋅ √n), and a lower bound of $Ω(k) for k ∈ 𝒪(√n)$, which can be as large as $Ω(√n$). For unit interval graphs it is known that some recoloring is needed even if we have k+1 colors available. We give an algorithm that maintains a (k+1)-coloring with at most $𝒪(k²)$ recolorings per step in the worst case. We also give a lower bound of $Ω(log n)$ on the amortized recourse budget needed to maintain a k-coloring. Additionally, for general interval graphs we show that if one does not insist on maintaining an explicit coloring, one can have a k-coloring algorithm which does not incur a factor of $𝒪(k ⋅ k! ⋅ √n)$ in the running time. For this we provide a data structure, which allows for adding intervals in $𝒪(k² log³ n)$ amortized time per update and querying for the color of a particular interval in $𝒪(log n) time$. Between any two updates, the data structure answers consistently with some optimal coloring. The data structure maintains the coloring implicitly, so the notion of recourse budget does not apply to it.
dc.affiliationpl
Wydział Matematyki i Informatyki : Instytut Informatyki Analitycznej
dc.conferencepl
17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020)
dc.conference.city
Tórshavn
dc.conference.country
Faroe Islands
dc.conference.datefinish
2020-07-24
dc.conference.datestart
2020-07-22
dc.contributor.authorpl
Bosek, Bartłomiej - 114402
dc.contributor.authorpl
Disser, Yann
dc.contributor.authorpl
Feldmann, Andreas Emil
dc.contributor.authorpl
Pawlewicz, Jakub
dc.contributor.authorpl
Zych-Pawlewicz, Anna
dc.date.accessioned
2020-11-07T18:00:12Z
dc.date.available
2020-11-07T18:00:12Z
dc.date.issuedpl
2020
dc.date.openaccess
0
dc.description.accesstime
w momencie opublikowania
dc.description.conftypepl
international
dc.description.physicalpl
17:1-17:23
dc.description.publicationpl
0,9
dc.description.series
Leibniz International Proceedings in Informatics (LIPIcs)
dc.description.seriesnumber
162
dc.description.version
ostateczna wersja wydawcy
dc.identifier.doipl
10.4230/LIPIcs.SWAT.2020.17
dc.identifier.isbnpl
978-3-95977-150-4
dc.identifier.projectpl
2017/26/D/ST6/00264
dc.identifier.projectpl
2017/26/D/ST6/00264
dc.identifier.projectpl
ROD UJ / OP
dc.identifier.seriesissn
1868-8969
dc.identifier.uri
https://ruj.uj.edu.pl/xmlui/handle/item/252948
dc.languagepl
eng
dc.language.containerpl
eng
dc.pubinfopl
Dagstuhl : Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik
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.subtypepl
ConferenceProceedings
dc.titlepl
Recoloring interval graphs with limited recourse budget
dc.title.containerpl
17th Scandinavian symposium and workshops on algorithm theory (SWAT 2020)
dc.typepl
BookSection
dspace.entity.type
Publication
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
bosek_et-al_recoloring_interval_graphs_2020.pdf
3