6 Search Results for "Bosek, Bartłomiej"

Document
Invited Talk
DOI: 10.4230/LIPIcs.ESA.2024.2
Simple (Invited Talk)

Authors: Eva Rotenberg

Published in: LIPIcs, Volume 308, 32nd Annual European Symposium on Algorithms (ESA 2024)

Abstract
Simplicity in algorithms has various aspects; interpretations and implications. One is the simplicity of the algorithmic solution itself: if an algorithm (or data structure) has a brief verbal description or can be written with few lines of pseudocode, this can lead to easier, more robust, and possibly more efficient implementations. Another aspect of simplicity relates to the proofs of correctness and efficiency of our algorithmic solutions. Here, we experience that algorithms and data structures with simpler proofs of statements about their properties can be easier to understand, easier to teach, and sometimes, easier to generalise. Simplification of proofs also receives attention in mathematics; here, too, simplification has benefits to clarity of exposition and possibility of generalisation. There are even examples of proof simplification leading to the design of new and more efficient algorithms. This talk will present examples illustrating these various aspects of simplicity. Examples where algorithmic simplification or proof simplification has led to improved performance of algorithms and data structures, in theory, in practice, or both. Finally, some of the most attractive questions in discrete mathematics and in theory of computing have a property in common: they are very simple to pose, but surprisingly, to our knowledge, not very simple to answer. The talk will include examples of such questions, which I leave as an open problem for the audience.
Cite as

Eva Rotenberg. Simple (Invited Talk). In 32nd Annual European Symposium on Algorithms (ESA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 308, pp. 2:1-2:2, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{rotenberg:LIPIcs.ESA.2024.2,
  author =	{Rotenberg, Eva},
  title =	{{Simple}},
  booktitle =	{32nd Annual European Symposium on Algorithms (ESA 2024)},
  pages =	{2:1--2:2},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-338-6},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{308},
  editor =	{Chan, Timothy and Fischer, Johannes and Iacono, John and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2024.2},
  URN =		{urn:nbn:de:0030-drops-210739},
  doi =		{10.4230/LIPIcs.ESA.2024.2},
  annote =	{Keywords: Simplicity, graph algorithms, computational geometry, algorithmic simplification, data structures, combinatorics, proof simplification, dynamic graphs}
}
Document
DOI: 10.4230/LIPIcs.ESA.2024.81
Edge-Coloring Sparse Graphs with Δ Colors in Quasilinear Time

Authors: Łukasz Kowalik

Published in: LIPIcs, Volume 308, 32nd Annual European Symposium on Algorithms (ESA 2024)

Abstract
In this paper we show that every graph G of bounded maximum average degree mad(G) and with maximum degree Δ can be edge-colored using the optimal number of Δ colors in quasilinear time, whenever Δ ≥ 2mad(G). The maximum average degree is within a multiplicative constant of other popular graph sparsity parameters like arboricity, degeneracy or maximum density. Our algorithm extends previous results of Chrobak and Nishizeki [Marek Chrobak and Takao Nishizeki, 1990] and Bhattacharya, Costa, Panski and Solomon [Sayan Bhattacharya et al., 2023].
Cite as

Łukasz Kowalik. Edge-Coloring Sparse Graphs with Δ Colors in Quasilinear Time. In 32nd Annual European Symposium on Algorithms (ESA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 308, pp. 81:1-81:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{kowalik:LIPIcs.ESA.2024.81,
  author =	{Kowalik, {\L}ukasz},
  title =	{{Edge-Coloring Sparse Graphs with \Delta Colors in Quasilinear Time}},
  booktitle =	{32nd Annual European Symposium on Algorithms (ESA 2024)},
  pages =	{81:1--81:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-338-6},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{308},
  editor =	{Chan, Timothy and Fischer, Johannes and Iacono, John and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2024.81},
  URN =		{urn:nbn:de:0030-drops-211523},
  doi =		{10.4230/LIPIcs.ESA.2024.81},
  annote =	{Keywords: edge coloring, algorithm, sparse, graph, quasilinear}
}
Document
DOI: 10.4230/LIPIcs.ESA.2024.95
Competitive Capacitated Online Recoloring

Authors: Rajmohan Rajaraman and Omer Wasim

Published in: LIPIcs, Volume 308, 32nd Annual European Symposium on Algorithms (ESA 2024)

Abstract
In this paper, we revisit the online recoloring problem introduced recently by Azar, Machluf, Patt-Shamir and Touitou [Azar et al., 2022] to investigate algorithmic challenges that arise while scheduling virtual machines or processes in distributed systems and cloud services. In online recoloring, there is a fixed set V of n vertices and an initial coloring c₀: V → [k] for some k ∈ ℤ^{> 0}. Under an online sequence σ of requests where each request is an edge (u_t,v_t), a proper vertex coloring c of the graph G_t induced by requests until time t needs to be maintained for all t; i.e., for any (u,v) ∈ G_t, c(u)≠ c(v). In the distributed systems application, a vertex corresponds to a VM, an edge corresponds to the requirement that the two endpoint VMs be on different clusters, and a coloring is an allocation of VMs to clusters. The objective is to minimize the total weight of vertices recolored for the sequence σ. In [Azar et al., 2022], the authors give competitive algorithms for two polynomially tractable cases - 2-coloring for bipartite G_t and (Δ+1)-coloring for Δ-degree G_t - and lower bounds for the fully dynamic case where G_t can be arbitrary. We obtain the first competitive algorithms for capacitated online recoloring and fully dynamic recoloring, in which there is a bound on the number or weight of vertices in each color. Our first set of results is for 2-recoloring using algorithms that are (1+ε)-resource augmented where ε ∈ (0,1) is an arbitrarily small constant. Our main result is an O(log n)-competitive deterministic algorithm for weighted bipartite graphs, which is asymptotically optimal in light of an Ω(log n) lower bound that holds for an unbounded amount of augmentation. We also present an O(nlog n)-competitive deterministic algorithm for fully dynamic recoloring, which is optimal within an O(log n) factor in light of a Ω(n) lower bound that holds for an unbounded amount of augmentation. Our second set of results is for Δ-recoloring in an (1+ε)-overprovisioned setting where the maximum degree of G_t is bounded by (1-ε)Δ for all t, and each color assigned to at most (1+ε)n/(Δ) vertices, for an arbitrary ε > 0. Our main result is an O(1)-competitive randomized algorithm for Δ = O(√{n/log n}). We also present an O(Δ)-competitive deterministic algorithm for Δ ≤ ε n/2. Both results are asymptotically optimal.
Cite as

Rajmohan Rajaraman and Omer Wasim. Competitive Capacitated Online Recoloring. In 32nd Annual European Symposium on Algorithms (ESA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 308, pp. 95:1-95:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{rajaraman_et_al:LIPIcs.ESA.2024.95,
  author =	{Rajaraman, Rajmohan and Wasim, Omer},
  title =	{{Competitive Capacitated Online Recoloring}},
  booktitle =	{32nd Annual European Symposium on Algorithms (ESA 2024)},
  pages =	{95:1--95:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-338-6},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{308},
  editor =	{Chan, Timothy and Fischer, Johannes and Iacono, John and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2024.95},
  URN =		{urn:nbn:de:0030-drops-211666},
  doi =		{10.4230/LIPIcs.ESA.2024.95},
  annote =	{Keywords: online algorithms, competitive ratio, recoloring, resource augmentation}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2024.33
First-Fit Coloring of Forests in Random Arrival Model

Authors: Bartłomiej Bosek, Grzegorz Gutowski, Michał Lasoń, and Jakub Przybyło

Published in: LIPIcs, Volume 306, 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024)

Abstract
We consider a graph coloring algorithm that processes vertices in order taken uniformly at random and assigns colors to them using First-Fit strategy. We show that this algorithm uses, in expectation, at most (1+o(1))⋅ln n / ln ln n different colors to color any forest with n vertices. We also construct a family of forests that shows that this bound is best possible.
Cite as

Bartłomiej Bosek, Grzegorz Gutowski, Michał Lasoń, and Jakub Przybyło. First-Fit Coloring of Forests in Random Arrival Model. In 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 306, pp. 33:1-33:10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{bosek_et_al:LIPIcs.MFCS.2024.33,
  author =	{Bosek, Bart{\l}omiej and Gutowski, Grzegorz and Laso\'{n}, Micha{\l} and Przyby{\l}o, Jakub},
  title =	{{First-Fit Coloring of Forests in Random Arrival Model}},
  booktitle =	{49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024)},
  pages =	{33:1--33:10},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-335-5},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{306},
  editor =	{Kr\'{a}lovi\v{c}, Rastislav and Ku\v{c}era, Anton{\'\i}n},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2024.33},
  URN =		{urn:nbn:de:0030-drops-205892},
  doi =		{10.4230/LIPIcs.MFCS.2024.33},
  annote =	{Keywords: First-Fit, Online Algorithms, Graph Coloring, Random Arrival Model}
}
Document
DOI: 10.4230/LIPIcs.ESA.2022.25
Dynamic Coloring of Unit Interval Graphs with Limited Recourse Budget

Authors: Bartłomiej Bosek and Anna Zych-Pawlewicz

Published in: LIPIcs, Volume 244, 30th Annual European Symposium on Algorithms (ESA 2022)

Abstract
In this paper we study the problem of coloring a unit interval graph which changes dynamically. In our model the unit intervals are added or removed one at the time, and have to be colored immediately, so that no two overlapping intervals share the same color. After each update only a limited number of intervals are allowed to be recolored. The limit on the number of recolorings per update is called the recourse budget. In this paper we show, that if the graph remains k-colorable at all times, the updates consist of insertions only, and the final instance consists of n intervals, then we can achieve an amortized recourse budget of 𝒪({k⁷ log n}) while maintaining a proper coloring with k colors. This is an exponential improvement over the result in [Bartłomiej Bosek et al., 2020] in terms of both k and n. We complement this result by showing the lower bound of Ω(n) on the amortized recourse budget in the fully dynamic setting. Our incremental algorithm can be efficiently implemented. As an additional application of our techniques we include a new combinatorial result on coloring unit circular arc graphs. Let L be the maximum number of arcs intersecting in one point for some set of unit circular arcs 𝒜. We show that if there is a set 𝒜' of non-intersecting unit arcs of size L²-1 such that 𝒜 ∪ 𝒜' does not contain L+1 arcs intersecting in one point, then it is possible to color 𝒜 with L colors. This complements the work on circular arc coloring [Belkale and Chandran, 2009; Tucker, 1975; Valencia-Pabon, 2003], which specifies sufficient conditions needed to color 𝒜 with L+1 colors or more.
Cite as

Bartłomiej Bosek and Anna Zych-Pawlewicz. Dynamic Coloring of Unit Interval Graphs with Limited Recourse Budget. In 30th Annual European Symposium on Algorithms (ESA 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 244, pp. 25:1-25:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{bosek_et_al:LIPIcs.ESA.2022.25,
  author =	{Bosek, Bart{\l}omiej and Zych-Pawlewicz, Anna},
  title =	{{Dynamic Coloring of Unit Interval Graphs with Limited Recourse Budget}},
  booktitle =	{30th Annual European Symposium on Algorithms (ESA 2022)},
  pages =	{25:1--25:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-247-1},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{244},
  editor =	{Chechik, Shiri and Navarro, Gonzalo and Rotenberg, Eva and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2022.25},
  URN =		{urn:nbn:de:0030-drops-169637},
  doi =		{10.4230/LIPIcs.ESA.2022.25},
  annote =	{Keywords: dynamic algorithms, unit interval graphs, coloring, recourse budget, parametrized dynamic algorithms}
}
Document
DOI: 10.4230/LIPIcs.SWAT.2020.17
Recoloring Interval Graphs with Limited Recourse Budget

Authors: Bartłomiej Bosek, Yann Disser, Andreas Emil Feldmann, Jakub Pawlewicz, and Anna Zych-Pawlewicz

Published in: LIPIcs, Volume 162, 17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020)

Abstract
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.
Cite as

Bartłomiej Bosek, Yann Disser, Andreas Emil Feldmann, Jakub Pawlewicz, and Anna Zych-Pawlewicz. Recoloring Interval Graphs with Limited Recourse Budget. In 17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 162, pp. 17:1-17:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{bosek_et_al:LIPIcs.SWAT.2020.17,
  author =	{Bosek, Bart{\l}omiej and Disser, Yann and Feldmann, Andreas Emil and Pawlewicz, Jakub and Zych-Pawlewicz, Anna},
  title =	{{Recoloring Interval Graphs with Limited Recourse Budget}},
  booktitle =	{17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020)},
  pages =	{17:1--17:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-150-4},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{162},
  editor =	{Albers, Susanne},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2020.17},
  URN =		{urn:nbn:de:0030-drops-122649},
  doi =		{10.4230/LIPIcs.SWAT.2020.17},
  annote =	{Keywords: Colouring, Dynamic Algorithms, Recourse Budget, Interval Graphs}
}
  • Refine by Author
  • 3 Bosek, Bartłomiej
  • 2 Zych-Pawlewicz, Anna
  • 1 Disser, Yann
  • 1 Feldmann, Andreas Emil
  • 1 Gutowski, Grzegorz
  • Show More...

  • Refine by Classification
  • 2 Theory of computation → Design and analysis of algorithms
  • 2 Theory of computation → Online algorithms
  • 1 Mathematics of computing → Graph coloring
  • 1 Theory of computation
  • 1 Theory of computation → Data structures design and analysis
  • Show More...

  • Refine by Keyword
  • 1 Colouring
  • 1 Dynamic Algorithms
  • 1 First-Fit
  • 1 Graph Coloring
  • 1 Interval Graphs
  • Show More...

  • Refine by Type
  • 6 document

  • Refine by Publication Year
  • 4 2024
  • 1 2020
  • 1 2022

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact