94 Search Results for "Sankowski, Piotr"


Volume

LIPIcs, Volume 57

24th Annual European Symposium on Algorithms (ESA 2016)

ESA 2016, August 22-24, 2016, Aarhus, Denmark

Editors: Piotr Sankowski and Christos Zaroliagis

Document
Track A: Algorithms, Complexity and Games
Fully Dynamic Shortest Paths and Reachability in Sparse Digraphs

Authors: Adam Karczmarz and Piotr Sankowski

Published in: LIPIcs, Volume 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)


Abstract
We study the exact fully dynamic shortest paths problem. For real-weighted directed graphs, we show a deterministic fully dynamic data structure with Õ(mn^{4/5}) worst-case update time processing arbitrary s,t-distance queries in Õ(n^{4/5}) time. This constitutes the first non-trivial update/query tradeoff for this problem in the regime of sparse weighted directed graphs. Moreover, we give a Monte Carlo randomized fully dynamic reachability data structure processing single-edge updates in Õ(n√m) worst-case time and queries in O(√m) time. For sparse digraphs, such a tradeoff has only been previously described with amortized update time [Roditty and Zwick, SIAM J. Comp. 2008].

Cite as

Adam Karczmarz and Piotr Sankowski. Fully Dynamic Shortest Paths and Reachability in Sparse Digraphs. In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 261, pp. 84:1-84:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)


Copy BibTex To Clipboard

@InProceedings{karczmarz_et_al:LIPIcs.ICALP.2023.84,
  author =	{Karczmarz, Adam and Sankowski, Piotr},
  title =	{{Fully Dynamic Shortest Paths and Reachability in Sparse Digraphs}},
  booktitle =	{50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)},
  pages =	{84:1--84:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-278-5},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{261},
  editor =	{Etessami, Kousha and Feige, Uriel and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2023.84},
  URN =		{urn:nbn:de:0030-drops-181363},
  doi =		{10.4230/LIPIcs.ICALP.2023.84},
  annote =	{Keywords: dynamic shortest paths, dynamic reachability, dynamic transitive closure}
}
Document
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-dev.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
Min-Cost Flow in Unit-Capacity Planar Graphs

Authors: Adam Karczmarz and Piotr Sankowski

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


Abstract
In this paper we give an O~((nm)^(2/3) log C) time algorithm for computing min-cost flow (or min-cost circulation) in unit capacity planar multigraphs where edge costs are integers bounded by C. For planar multigraphs, this improves upon the best known algorithms for general graphs: the O~(m^(10/7) log C) time algorithm of Cohen et al. [SODA 2017], the O(m^(3/2) log(nC)) time algorithm of Gabow and Tarjan [SIAM J. Comput. 1989] and the O~(sqrt(n) m log C) time algorithm of Lee and Sidford [FOCS 2014]. In particular, our result constitutes the first known fully combinatorial algorithm that breaks the Omega(m^(3/2)) time barrier for min-cost flow problem in planar graphs. To obtain our result we first give a very simple successive shortest paths based scaling algorithm for unit-capacity min-cost flow problem that does not explicitly operate on dual variables. This algorithm also runs in O~(m^(3/2) log C) time for general graphs, and, to the best of our knowledge, it has not been described before. We subsequently show how to implement this algorithm faster on planar graphs using well-established tools: r-divisions and efficient algorithms for computing (shortest) paths in so-called dense distance graphs.

Cite as

Adam Karczmarz and Piotr Sankowski. Min-Cost Flow in Unit-Capacity Planar Graphs. In 27th Annual European Symposium on Algorithms (ESA 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 144, pp. 66:1-66:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)


Copy BibTex To Clipboard

@InProceedings{karczmarz_et_al:LIPIcs.ESA.2019.66,
  author =	{Karczmarz, Adam and Sankowski, Piotr},
  title =	{{Min-Cost Flow in Unit-Capacity Planar Graphs}},
  booktitle =	{27th Annual European Symposium on Algorithms (ESA 2019)},
  pages =	{66:1--66:17},
  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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2019.66},
  URN =		{urn:nbn:de:0030-drops-111878},
  doi =		{10.4230/LIPIcs.ESA.2019.66},
  annote =	{Keywords: minimum-cost flow, minimum-cost circulation, planar graphs}
}
Document
Planar Maximum Matching: Towards a Parallel Algorithm

Authors: Samir Datta, Raghav Kulkarni, Ashish Kumar, and Anish Mukherjee

Published in: LIPIcs, Volume 123, 29th International Symposium on Algorithms and Computation (ISAAC 2018)


Abstract
Perfect matchings in planar graphs have been extensively studied and understood in the context of parallel complexity [P W Kastelyn, 1967; Vijay Vazirani, 1988; Meena Mahajan and Kasturi R. Varadarajan, 2000; Datta et al., 2010; Nima Anari and Vijay V. Vazirani, 2017]. However, corresponding results for maximum matchings have been elusive. We partly bridge this gap by proving: 1) An SPL upper bound for planar bipartite maximum matching search. 2) Planar maximum matching search reduces to planar maximum matching decision. 3) Planar maximum matching count reduces to planar bipartite maximum matching count and planar maximum matching decision. The first bound improves on the known [Thanh Minh Hoang, 2010] bound of L^{C_=L} and is adaptable to any special bipartite graph class with non-zero circulation such as bounded genus graphs, K_{3,3}-free graphs and K_5-free graphs. Our bounds and reductions non-trivially combine techniques like the Gallai-Edmonds decomposition [L. Lovász and M.D. Plummer, 1986], deterministic isolation [Datta et al., 2010; Samir Datta et al., 2012; Rahul Arora et al., 2016], and the recent breakthroughs in the parallel search for planar perfect matchings [Nima Anari and Vijay V. Vazirani, 2017; Piotr Sankowski, 2018].

Cite as

Samir Datta, Raghav Kulkarni, Ashish Kumar, and Anish Mukherjee. Planar Maximum Matching: Towards a Parallel Algorithm. In 29th International Symposium on Algorithms and Computation (ISAAC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 123, pp. 21:1-21:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)


Copy BibTex To Clipboard

@InProceedings{datta_et_al:LIPIcs.ISAAC.2018.21,
  author =	{Datta, Samir and Kulkarni, Raghav and Kumar, Ashish and Mukherjee, Anish},
  title =	{{Planar Maximum Matching: Towards a Parallel Algorithm}},
  booktitle =	{29th International Symposium on Algorithms and Computation (ISAAC 2018)},
  pages =	{21:1--21:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-094-1},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{123},
  editor =	{Hsu, Wen-Lian and Lee, Der-Tsai and Liao, Chung-Shou},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2018.21},
  URN =		{urn:nbn:de:0030-drops-99695},
  doi =		{10.4230/LIPIcs.ISAAC.2018.21},
  annote =	{Keywords: maximum matching, planar graphs, parallel complexity, reductions}
}
Document
Online Facility Location with Deletions

Authors: Marek Cygan, Artur Czumaj, Marcin Mucha, and Piotr Sankowski

Published in: LIPIcs, Volume 112, 26th Annual European Symposium on Algorithms (ESA 2018)


Abstract
In this paper we study three previously unstudied variants of the online Facility Location problem, considering an intrinsic scenario when the clients and facilities are not only allowed to arrive to the system, but they can also depart at any moment. We begin with the study of a natural fully-dynamic online uncapacitated model where clients can be both added and removed. When a client arrives, then it has to be assigned either to an existing facility or to a new facility opened at the client's location. However, when a client who has been also one of the open facilities is to be removed, then our model has to allow to reconnect all clients that have been connected to that removed facility. In this model, we present an optimal O(log(n_{act}) / log log(n_{act}))-competitive algorithm, where n_{act} is the number of active clients at the end of the input sequence. Next, we turn our attention to the capacitated Facility Location problem. We first note that if no deletions are allowed, then one can achieve an optimal competitive ratio of O(log(n) / log(log n)), where n is the length of the sequence. However, when deletions are allowed, the capacitated version of the problem is significantly more challenging than the uncapacitated one. We show that still, using a more sophisticated algorithmic approach, one can obtain an online O(log N + log c log n)-competitive algorithm for the capacitated Facility Location problem in the fully dynamic model, where N is number of points in the input metric and c is the capacity of any open facility.

Cite as

Marek Cygan, Artur Czumaj, Marcin Mucha, and Piotr Sankowski. Online Facility Location with Deletions. In 26th Annual European Symposium on Algorithms (ESA 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 112, pp. 21:1-21:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)


Copy BibTex To Clipboard

@InProceedings{cygan_et_al:LIPIcs.ESA.2018.21,
  author =	{Cygan, Marek and Czumaj, Artur and Mucha, Marcin and Sankowski, Piotr},
  title =	{{Online Facility Location with Deletions}},
  booktitle =	{26th Annual European Symposium on Algorithms (ESA 2018)},
  pages =	{21:1--21:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-081-1},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{112},
  editor =	{Azar, Yossi and Bast, Hannah and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2018.21},
  URN =		{urn:nbn:de:0030-drops-94843},
  doi =		{10.4230/LIPIcs.ESA.2018.21},
  annote =	{Keywords: online algorithms, facility location, fully-dynamic online algorithms}
}
Document
NC Algorithms for Weighted Planar Perfect Matching and Related Problems

Authors: Piotr Sankowski

Published in: LIPIcs, Volume 107, 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)


Abstract
Consider a planar graph G=(V,E) with polynomially bounded edge weight function w:E -> [0, poly(n)]. The main results of this paper are NC algorithms for finding minimum weight perfect matching in G. In order to solve this problems we develop a new relatively simple but versatile framework that is combinatorial in spirit. It handles the combinatorial structure of matchings directly and needs to only know weights of appropriately defined matchings from algebraic subroutines. Moreover, using novel planarity preserving reductions, we show how to find: maximum weight matching in G when G is bipartite; maximum multiple-source multiple-sink flow in G where c:E -> [1, poly(n)] is a polynomially bounded edge capacity function; minimum weight f-factor in G where f:V -> [1, poly(n)]; min-cost flow in G where c:E -> [1, poly(n)] is a polynomially bounded edge capacity function and b:V -> [1, poly(n)] is a polynomially bounded vertex demand function. There have been no known NC algorithms for these problems previously.

Cite as

Piotr Sankowski. NC Algorithms for Weighted Planar Perfect Matching and Related Problems. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 107, pp. 97:1-97:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)


Copy BibTex To Clipboard

@InProceedings{sankowski:LIPIcs.ICALP.2018.97,
  author =	{Sankowski, Piotr},
  title =	{{NC Algorithms for Weighted Planar Perfect Matching and Related Problems}},
  booktitle =	{45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)},
  pages =	{97:1--97:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-076-7},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{107},
  editor =	{Chatzigiannakis, Ioannis and Kaklamanis, Christos and Marx, D\'{a}niel and Sannella, Donald},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2018.97},
  URN =		{urn:nbn:de:0030-drops-91011},
  doi =		{10.4230/LIPIcs.ICALP.2018.97},
  annote =	{Keywords: planar graph, NC algorithms, maximum cardinality matching, maximum weight matching, min-cost flow, maximum multiple-source multiple-sink flow, f-factors}
}
Document
Approximate Nearest Neighbors Search Without False Negatives For l_2 For c>sqrt{loglog{n}}

Authors: Piotr Sankowski and Piotr Wygocki

Published in: LIPIcs, Volume 92, 28th International Symposium on Algorithms and Computation (ISAAC 2017)


Abstract
In this paper, we report progress on answering the open problem presented by Pagh [11], who considered the near neighbor search without false negatives for the Hamming distance. We show new data structures for solving the c-approximate near neighbors problem without false negatives for Euclidean high dimensional space \mathcal{R}^d. These data structures work for any c = \omega(\sqrt{\log{\log{n}}}), where n is the number of points in the input set, with poly-logarithmic query time and polynomial pre-processing time. This improves over the known algorithms, which require c to be \Omega(\sqrt{d}). This improvement is obtained by applying a sequence of reductions, which are interesting on their own. First, we reduce the problem to d instances of dimension logarithmic in n. Next, these instances are reduced to a number of c-approximate near neighbor search without false negatives instances in \big(\Rspace^k\big)^L space equipped with metric m(x,y) = \max_{1 \le i \leL}(\dist{x_i - y_i}_2).

Cite as

Piotr Sankowski and Piotr Wygocki. Approximate Nearest Neighbors Search Without False Negatives For l_2 For c>sqrt{loglog{n}}. In 28th International Symposium on Algorithms and Computation (ISAAC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 92, pp. 63:1-63:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)


Copy BibTex To Clipboard

@InProceedings{sankowski_et_al:LIPIcs.ISAAC.2017.63,
  author =	{Sankowski, Piotr and Wygocki, Piotr},
  title =	{{Approximate Nearest Neighbors Search Without False Negatives For l\underline2 For c\ranglesqrt\{loglog\{n\}\}}},
  booktitle =	{28th International Symposium on Algorithms and Computation (ISAAC 2017)},
  pages =	{63:1--63:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-054-5},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{92},
  editor =	{Okamoto, Yoshio and Tokuyama, Takeshi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2017.63},
  URN =		{urn:nbn:de:0030-drops-82189},
  doi =		{10.4230/LIPIcs.ISAAC.2017.63},
  annote =	{Keywords: locality sensitive hashing, approximate near neighbor search, high- dimensional, similarity search}
}
Document
Contracting a Planar Graph Efficiently

Authors: Jacob Holm, Giuseppe F. Italiano, Adam Karczmarz, Jakub Lacki, Eva Rotenberg, and Piotr Sankowski

Published in: LIPIcs, Volume 87, 25th Annual European Symposium on Algorithms (ESA 2017)


Abstract
We present a data structure that can maintain a simple planar graph under edge contractions in linear total time. The data structure supports adjacency queries and provides access to neighbor lists in O(1) time. Moreover, it can report all the arising self-loops and parallel edges. By applying the data structure, we can achieve optimal running times for decremental bridge detection, 2-edge connectivity, maximal 3-edge connected components, and the problem of finding a unique perfect matching for a static planar graph. Furthermore, we improve the running times of algorithms for several planar graph problems, including decremental 2-vertex and 3-edge connectivity, and we show that using our data structure in a black-box manner, one obtains conceptually simple optimal algorithms for computing MST and 5-coloring in planar graphs.

Cite as

Jacob Holm, Giuseppe F. Italiano, Adam Karczmarz, Jakub Lacki, Eva Rotenberg, and Piotr Sankowski. Contracting a Planar Graph Efficiently. In 25th Annual European Symposium on Algorithms (ESA 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 87, pp. 50:1-50:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)


Copy BibTex To Clipboard

@InProceedings{holm_et_al:LIPIcs.ESA.2017.50,
  author =	{Holm, Jacob and Italiano, Giuseppe F. and Karczmarz, Adam and Lacki, Jakub and Rotenberg, Eva and Sankowski, Piotr},
  title =	{{Contracting a Planar Graph Efficiently}},
  booktitle =	{25th Annual European Symposium on Algorithms (ESA 2017)},
  pages =	{50:1--50:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-049-1},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{87},
  editor =	{Pruhs, Kirk and Sohler, Christian},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2017.50},
  URN =		{urn:nbn:de:0030-drops-78755},
  doi =		{10.4230/LIPIcs.ESA.2017.50},
  annote =	{Keywords: planar graphs, algorithms, data structures, connectivity, coloring}
}
Document
Conditional Lower Bounds for All-Pairs Max-Flow

Authors: Robert Krauthgamer and Ohad Trabelsi

Published in: LIPIcs, Volume 80, 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)


Abstract
We provide evidence that computing the maximum flow value between every pair of nodes in a directed graph on n nodes, m edges, and capacities in the range [1..n], which we call the All-Pairs Max-Flow problem, cannot be solved in time that is faster significantly (i.e., by a polynomial factor) than O(n^2 m). Since a single maximum st-flow in such graphs can be solved in time \tilde{O}(m\sqrt{n}) [Lee and Sidford, FOCS 2014], we conclude that the all-pairs version might require time equivalent to \tilde\Omega(n^{3/2}) computations of maximum st-flow, which strongly separates the directed case from the undirected one. Moreover, if maximum $st$-flow can be solved in time \tilde{O}(m), then the runtime of \tilde\Omega(n^2) computations is needed. This is in contrast to a conjecture of Lacki, Nussbaum, Sankowski, and Wulf-Nilsen [FOCS 2012] that All-Pairs Max-Flow in general graphs can be solved faster than the time of O(n^2) computations of maximum st-flow. Specifically, we show that in sparse graphs G=(V,E,w), if one can compute the maximum st-flow from every s in an input set of sources S\subseteq V to every t in an input set of sinks T\subseteq V in time O((|S||T|m)^{1-epsilon}), for some |S|, |T|, and a constant epsilon>0, then MAX-CNF-SAT (maximum satisfiability of conjunctive normal form formulas) with n' variables and m' clauses can be solved in time {m'}^{O(1)}2^{(1-delta)n'} for a constant delta(epsilon)>0, a problem for which not even 2^{n'}/\poly(n') algorithms are known. Such runtime for MAX-CNF-SAT would in particular refute the Strong Exponential Time Hypothesis (SETH). Hence, we improve the lower bound of Abboud, Vassilevska-Williams, and Yu [STOC 2015], who showed that for every fixed epsilon>0 and |S|=|T|=O(\sqrt{n}), if the above problem can be solved in time O(n^{3/2-epsilon}), then some incomparable (and intuitively weaker) conjecture is false. Furthermore, a larger lower bound than ours implies strictly super-linear time for maximum st-flow problem, which would be an amazing breakthrough. In addition, we show that All-Pairs Max-Flow in uncapacitated networks with every edge-density m=m(n), cannot be computed in time significantly faster than O(mn), even for acyclic networks. The gap to the fastest known algorithm by Cheung, Lau, and Leung [FOCS 2011] is a factor of O(m^{omega-1}/n), and for acyclic networks it is O(n^{omega-1}), where omega is the matrix multiplication exponent.

Cite as

Robert Krauthgamer and Ohad Trabelsi. Conditional Lower Bounds for All-Pairs Max-Flow. In 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 80, pp. 20:1-20:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)


Copy BibTex To Clipboard

@InProceedings{krauthgamer_et_al:LIPIcs.ICALP.2017.20,
  author =	{Krauthgamer, Robert and Trabelsi, Ohad},
  title =	{{Conditional Lower Bounds for All-Pairs Max-Flow}},
  booktitle =	{44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)},
  pages =	{20:1--20:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-041-5},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{80},
  editor =	{Chatzigiannakis, Ioannis and Indyk, Piotr and Kuhn, Fabian and Muscholl, Anca},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2017.20},
  URN =		{urn:nbn:de:0030-drops-74264},
  doi =		{10.4230/LIPIcs.ICALP.2017.20},
  annote =	{Keywords: Conditional lower bounds, Hardness in P, All-Pairs Maximum Flow, Strong Exponential Time Hypothesis}
}
Document
Improved Distance Queries and Cycle Counting by Frobenius Normal Form

Authors: Piotr Sankowski and Karol Wegrzycki

Published in: LIPIcs, Volume 66, 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017)


Abstract
Consider an unweighted, directed graph G with the diameter D. In this paper, we introduce the framework for counting cycles and walks of given length in matrix multiplication time O-tilde(n^omega). The framework is based on the fast decomposition into Frobenius normal form and the Hankel matrix-vector multiplication. It allows us to solve the following problems efficiently. * All Nodes Shortest Cycles - for every node return the length of the shortest cycle containing it. We give an O-tilde(n^omega) algorithm that improves the previous O-tilde(n^((omega + 3)/2)) algorithm for unweighted digraphs. * We show how to compute all D sets of vertices lying on cycles of length c in {1, ..., D} in randomized time O-tilde(n^omega). It improves upon an algorithm by Cygan where algorithm that computes a single set is presented. * We present a functional improvement of distance queries for directed, unweighted graphs. * All Pairs All Walks - we show almost optimal O-tilde(n^3) time algorithm for all walks counting problem. We improve upon the naive O(D n^omega) time algorithm.

Cite as

Piotr Sankowski and Karol Wegrzycki. Improved Distance Queries and Cycle Counting by Frobenius Normal Form. In 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 66, pp. 56:1-56:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)


Copy BibTex To Clipboard

@InProceedings{sankowski_et_al:LIPIcs.STACS.2017.56,
  author =	{Sankowski, Piotr and Wegrzycki, Karol},
  title =	{{Improved Distance Queries and Cycle Counting by Frobenius Normal Form}},
  booktitle =	{34th Symposium on Theoretical Aspects of Computer Science (STACS 2017)},
  pages =	{56:1--56:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-028-6},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{66},
  editor =	{Vollmer, Heribert and Vall\'{e}e, Brigitte},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2017.56},
  URN =		{urn:nbn:de:0030-drops-69773},
  doi =		{10.4230/LIPIcs.STACS.2017.56},
  annote =	{Keywords: Frobenius Normal Form, Graph Algorithms, All Nodes Shortest Cycles}
}
Document
Complete Volume
LIPIcs, Volume 57, ESA'16, Complete Volume

Authors: Piotr Sankowski and Christos Zaroliagis

Published in: LIPIcs, Volume 57, 24th Annual European Symposium on Algorithms (ESA 2016)


Abstract
LIPIcs, Volume 57, ESA'16, Complete Volume

Cite as

24th Annual European Symposium on Algorithms (ESA 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 57, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)


Copy BibTex To Clipboard

@Proceedings{sankowski_et_al:LIPIcs.ESA.2016,
  title =	{{LIPIcs, Volume 57, ESA'16, Complete Volume}},
  booktitle =	{24th Annual European Symposium on Algorithms (ESA 2016)},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-015-6},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{57},
  editor =	{Sankowski, Piotr and Zaroliagis, Christos},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2016},
  URN =		{urn:nbn:de:0030-drops-65854},
  doi =		{10.4230/LIPIcs.ESA.2016},
  annote =	{Keywords: Data Structures, Nonnumerical Algorithms and Problems, Optimization, Discrete Mathematics, Mathematical Software, Algorithms, Problem Solving, Control Methods and Search, Computational Geometry and Object Modeling}
}
Document
Front Matter
Front Matter, Table of Contents, Preface, Programm Commitee, External Reviewers

Authors: Piotr Sankowski and Christos Zaroliagis

Published in: LIPIcs, Volume 57, 24th Annual European Symposium on Algorithms (ESA 2016)


Abstract
Front Matter, Table of Contents, Preface, Programm Commitee, External Reviewers

Cite as

24th Annual European Symposium on Algorithms (ESA 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 57, pp. 0:i-0:xxiv, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)


Copy BibTex To Clipboard

@InProceedings{sankowski_et_al:LIPIcs.ESA.2016.0,
  author =	{Sankowski, Piotr and Zaroliagis, Christos},
  title =	{{Front Matter, Table of Contents, Preface, Programm Commitee, External Reviewers}},
  booktitle =	{24th Annual European Symposium on Algorithms (ESA 2016)},
  pages =	{0:i--0:xxiv},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-015-6},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{57},
  editor =	{Sankowski, Piotr and Zaroliagis, Christos},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2016.0},
  URN =		{urn:nbn:de:0030-drops-63429},
  doi =		{10.4230/LIPIcs.ESA.2016.0},
  annote =	{Keywords: Front Matter, Table of Contents, Preface, Programm Commitee, External Reviewers}
}
Document
Invited Talk
2-Connectivity in Directed Graphs (Invited Talk)

Authors: Loukas Georgiadis, Giuseppe F. Italiano, and Nikos Parotsidis

Published in: LIPIcs, Volume 57, 24th Annual European Symposium on Algorithms (ESA 2016)


Abstract
We survey some recent results on 2-edge and 2-vertex connectivity problems in directed graphs. Despite being complete analogs of the corresponding notions on undirected graphs, in digraphs 2-vertex and 2-edge connectivity have a much richer and more complicated structure. It is thus not surprising that 2-connectivity problems on directed graphs appear to be more difficult than on undirected graphs. For undirected graphs it has been known for over 40 years how to compute all bridges, articulation points, 2-edge- and 2-vertex-connected components in linear time, by simply using depth-first search. In the case of digraphs, however, the very same problems have been much more challenging and required the development of new tools and techniques.

Cite as

Loukas Georgiadis, Giuseppe F. Italiano, and Nikos Parotsidis. 2-Connectivity in Directed Graphs (Invited Talk). In 24th Annual European Symposium on Algorithms (ESA 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 57, pp. 1:1-1:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)


Copy BibTex To Clipboard

@InProceedings{georgiadis_et_al:LIPIcs.ESA.2016.1,
  author =	{Georgiadis, Loukas and Italiano, Giuseppe F. and Parotsidis, Nikos},
  title =	{{2-Connectivity in Directed Graphs}},
  booktitle =	{24th Annual European Symposium on Algorithms (ESA 2016)},
  pages =	{1:1--1:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-015-6},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{57},
  editor =	{Sankowski, Piotr and Zaroliagis, Christos},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2016.1},
  URN =		{urn:nbn:de:0030-drops-63451},
  doi =		{10.4230/LIPIcs.ESA.2016.1},
  annote =	{Keywords: 2-edge and 2-vertex connectivity on directed graphs, graph algorithms, dominator trees}
}
Document
Invited Talk
Algorithms with Provable Guarantees for Clustering (Invited Talk)

Authors: Ola Svensson

Published in: LIPIcs, Volume 57, 24th Annual European Symposium on Algorithms (ESA 2016)


Abstract
In this talk, we give an overview of the current best approximation algorithms for fundamental clustering problems, such as k-center, k-median, k-means, and facility location. We focus on recent progress and point out several important open problems. For the uncapacitated versions, a variety of algorithmic methodologies, such as LP-rounding and primal-dual method, have been applied to a standard linear programming relaxation. This has given a uniform way of addressing these problems resulting in small constant approximation guarantees. In spite of this impressive progress, it remains a challenging open problem to give tight guarantees. Moreover, this collection of powerful algorithmic techniques is not easily applicable to the capacitated setting. In fact, there is no simple strong convex relaxation known for the capacitated versions. As a result, our understanding of these problems is significantly weaker and several fundamental questions remain open.

Cite as

Ola Svensson. Algorithms with Provable Guarantees for Clustering (Invited Talk). In 24th Annual European Symposium on Algorithms (ESA 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 57, p. 2:1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)


Copy BibTex To Clipboard

@InProceedings{svensson:LIPIcs.ESA.2016.2,
  author =	{Svensson, Ola},
  title =	{{Algorithms with Provable Guarantees for Clustering}},
  booktitle =	{24th Annual European Symposium on Algorithms (ESA 2016)},
  pages =	{2:1--2:1},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-015-6},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{57},
  editor =	{Sankowski, Piotr and Zaroliagis, Christos},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2016.2},
  URN =		{urn:nbn:de:0030-drops-63435},
  doi =		{10.4230/LIPIcs.ESA.2016.2},
  annote =	{Keywords: Approximation algorithms, clustering}
}
  • Refine by Author
  • 13 Sankowski, Piotr
  • 4 Karczmarz, Adam
  • 4 Porat, Ely
  • 3 Bläsius, Thomas
  • 3 Friedrich, Tobias
  • Show More...

  • Refine by Classification
  • 2 Theory of computation → Network flows
  • 1 Theory of computation → Design and analysis of algorithms
  • 1 Theory of computation → Dynamic graph algorithms
  • 1 Theory of computation → Online algorithms
  • 1 Theory of computation → Parallel algorithms
  • Show More...

  • Refine by Keyword
  • 6 approximation algorithms
  • 5 planar graphs
  • 4 Approximation algorithms
  • 3 algorithms
  • 3 online algorithms
  • Show More...

  • Refine by Type
  • 93 document
  • 1 volume

  • Refine by Publication Year
  • 81 2016
  • 4 2017
  • 3 2018
  • 1 2011
  • 1 2013
  • Show More...

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