Recoloring interval graphs with limited recourse budget

2020
book section
conference proceedings
 cris.lastimport.wos 2024-04-09T20:20:38Z dc.abstract.en 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. pl dc.affiliation Wydział Matematyki i Informatyki : Instytut Informatyki Analitycznej pl dc.conference 17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020) pl dc.conference.city Tórshavn dc.conference.country Faroe Islands dc.conference.datefinish 2020-07-24 dc.conference.datestart 2020-07-22 dc.contributor.author Bosek, Bartłomiej - 114402 pl dc.contributor.author Disser, Yann pl dc.contributor.author Feldmann, Andreas Emil pl dc.contributor.author Pawlewicz, Jakub pl dc.contributor.author Zych-Pawlewicz, Anna pl dc.date.accessioned 2020-11-07T18:00:12Z dc.date.available 2020-11-07T18:00:12Z dc.date.issued 2020 pl dc.date.openaccess 0 dc.description.accesstime w momencie opublikowania dc.description.conftype international pl dc.description.physical 17:1-17:23 pl dc.description.publication 0,9 pl dc.description.series Leibniz International Proceedings in Informatics (LIPIcs) dc.description.seriesnumber 162 dc.description.version ostateczna wersja wydawcy dc.identifier.doi 10.4230/LIPIcs.SWAT.2020.17 pl dc.identifier.isbn 978-3-95977-150-4 pl dc.identifier.project 2017/26/D/ST6/00264 pl dc.identifier.project 2017/26/D/ST6/00264 pl dc.identifier.project ROD UJ / OP pl dc.identifier.seriesissn 1868-8969 dc.identifier.uri https://ruj.uj.edu.pl/xmlui/handle/item/252948 dc.language eng pl dc.language.container eng 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.subtype ConferenceProceedings pl dc.title Recoloring interval graphs with limited recourse budget pl dc.title.container 17th Scandinavian symposium and workshops on algorithm theory (SWAT 2020) pl dc.type BookSection pl dspace.entity.type Publication
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*
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