Search Results

Documents authored by Pawlewicz, Jakub

Document
DOI: 10.4230/LIPIcs.SoCG.2021.46
Sublinear Average-Case Shortest Paths in Weighted Unit-Disk Graphs

Authors: Adam Karczmarz, Jakub Pawlewicz, and Piotr Sankowski

Published in: LIPIcs, Volume 189, 37th International Symposium on Computational Geometry (SoCG 2021)

Abstract
We consider the problem of computing shortest paths in weighted unit-disk graphs in constant dimension d. Although the single-source and all-pairs variants of this problem are well-studied in the plane case, no non-trivial exact distance oracles for unit-disk graphs have been known to date, even for d = 2. The classical result of Sedgewick and Vitter [Algorithmica '86] shows that for weighted unit-disk graphs in the plane the A^* search has average-case performance superior to that of a standard shortest path algorithm, e.g., Dijkstra’s algorithm. Specifically, if the n corresponding points of a weighted unit-disk graph G are picked from a unit square uniformly at random, and the connectivity radius is r ∈ (0,1), A^* finds a shortest path in G in O(n) expected time when r = Ω(√{log n/n}), even though G has Θ((nr)²) edges in expectation. In other words, the work done by the algorithm is in expectation proportional to the number of vertices and not the number of edges. In this paper, we break this natural barrier and show even stronger sublinear time results. We propose a new heuristic approach to computing point-to-point exact shortest paths in unit-disk graphs. We analyze the average-case behavior of our heuristic using the same random graph model as used by Sedgewick and Vitter and prove it superior to A^*. Specifically, we show that, if we are able to report the set of all k points of G from an arbitrary rectangular region of the plane in O(k + t(n)) time, then a shortest path between arbitrary two points of such a random graph on the plane can be found in O(1/r² + t(n)) expected time. In particular, the state-of-the-art range reporting data structures imply a sublinear expected bound for all r = Ω(√{log n/n}) and O(√n) expected bound for r = Ω(n^{-1/4}) after only near-linear preprocessing of the point set. Our approach naturally generalizes to higher dimensions d ≥ 3 and yields sublinear expected bounds for all d = O(1) and sufficiently large r.
Cite as

Adam Karczmarz, Jakub Pawlewicz, and Piotr Sankowski. Sublinear Average-Case Shortest Paths in Weighted Unit-Disk Graphs. In 37th International Symposium on Computational Geometry (SoCG 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 189, pp. 46:1-46:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{karczmarz_et_al:LIPIcs.SoCG.2021.46,
  author =	{Karczmarz, Adam and Pawlewicz, Jakub and Sankowski, Piotr},
  title =	{{Sublinear Average-Case Shortest Paths in Weighted Unit-Disk Graphs}},
  booktitle =	{37th International Symposium on Computational Geometry (SoCG 2021)},
  pages =	{46:1--46:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-184-9},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{189},
  editor =	{Buchin, Kevin and Colin de Verdi\`{e}re, \'{E}ric},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2021.46},
  URN =		{urn:nbn:de:0030-drops-138454},
  doi =		{10.4230/LIPIcs.SoCG.2021.46},
  annote =	{Keywords: unit-disk graphs, shortest paths, distance oracles}
}
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}
}
Document
DOI: 10.4230/LIPIcs.ESA.2019.73
Equal-Subset-Sum Faster Than the Meet-in-the-Middle

Authors: Marcin Mucha, Jesper Nederlof, Jakub Pawlewicz, and Karol Węgrzycki

Published in: LIPIcs, Volume 144, 27th Annual European Symposium on Algorithms (ESA 2019)

Abstract
In the Equal-Subset-Sum problem, we are given a set S of n integers and the problem is to decide if there exist two disjoint nonempty subsets A,B subseteq S, whose elements sum up to the same value. The problem is NP-complete. The state-of-the-art algorithm runs in O^*(3^(n/2)) <= O^*(1.7321^n) time and is based on the meet-in-the-middle technique. In this paper, we improve upon this algorithm and give O^*(1.7088^n) worst case Monte Carlo algorithm. This answers a question suggested by Woeginger in his inspirational survey. Additionally, we analyse the polynomial space algorithm for Equal-Subset-Sum. A naive polynomial space algorithm for Equal-Subset-Sum runs in O^*(3^n) time. With read-only access to the exponentially many random bits, we show a randomized algorithm running in O^*(2.6817^n) time and polynomial space.
Cite as

Marcin Mucha, Jesper Nederlof, Jakub Pawlewicz, and Karol Węgrzycki. Equal-Subset-Sum Faster Than the Meet-in-the-Middle. In 27th Annual European Symposium on Algorithms (ESA 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 144, pp. 73:1-73:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{mucha_et_al:LIPIcs.ESA.2019.73,
  author =	{Mucha, Marcin and Nederlof, Jesper and Pawlewicz, Jakub and W\k{e}grzycki, Karol},
  title =	{{Equal-Subset-Sum Faster Than the Meet-in-the-Middle}},
  booktitle =	{27th Annual European Symposium on Algorithms (ESA 2019)},
  pages =	{73:1--73:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-124-5},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{144},
  editor =	{Bender, Michael A. and Svensson, Ola 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.2019.73},
  URN =		{urn:nbn:de:0030-drops-111946},
  doi =		{10.4230/LIPIcs.ESA.2019.73},
  annote =	{Keywords: Equal-Subset-Sum, Subset-Sum, meet-in-the-middle, enumeration technique, randomized algorithm}
}
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