174 Search Results for "Grandoni, Fabrizio"

Volume

LIPIcs, Volume 173

28th Annual European Symposium on Algorithms (ESA 2020)

ESA 2020, September 7-9, 2020, Pisa, Italy (Virtual Conference)

Editors: Fabrizio Grandoni, Grzegorz Herman, and Peter Sanders

Volume

LIPIcs, Volume 49

8th International Conference on Fun with Algorithms (FUN 2016)

FUN 2016, June 8-10, 2016, La Maddalena, Italy

Editors: Erik D. Demaine and Fabrizio Grandoni

Document
DOI: 10.4230/LIPIcs.ESA.2024.17
Cuts in Graphs with Matroid Constraints

Authors: Aritra Banik, Fedor V. Fomin, Petr A. Golovach, Tanmay Inamdar, Satyabrata Jana, and Saket Saurabh

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

Abstract
Vertex (s, t)-Cut and Vertex Multiway Cut are two fundamental graph separation problems in algorithmic graph theory. We study matroidal generalizations of these problems, where in addition to the usual input, we are given a representation R ∈ 𝔽^{r × n} of a linear matroid ℳ = (V(G), ℐ) of rank r in the input, and the goal is to determine whether there exists a vertex subset S ⊆ V(G) that has the required cut properties, as well as is independent in the matroid ℳ. We refer to these problems as Independent Vertex (s, t){-cut}, and Independent Multiway Cut, respectively. We show that these problems are fixed-parameter tractable (FPT) when parameterized by the solution size (which can be assumed to be equal to the rank of the matroid ℳ). These results are obtained by exploiting the recent technique of flow augmentation [Kim et al. STOC '22], combined with a dynamic programming algorithm on flow-paths á la [Feige and Mahdian, STOC '06] that maintains a representative family of solutions w.r.t. the given matroid [Marx, TCS '06; Fomin et al., JACM]. As a corollary, we also obtain FPT algorithms for the independent version of Odd Cycle Transversal. Further, our results can be generalized to other variants of the problems, e.g., weighted versions, or edge-deletion versions.
Cite as

Aritra Banik, Fedor V. Fomin, Petr A. Golovach, Tanmay Inamdar, Satyabrata Jana, and Saket Saurabh. Cuts in Graphs with Matroid Constraints. In 32nd Annual European Symposium on Algorithms (ESA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 308, pp. 17:1-17:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{banik_et_al:LIPIcs.ESA.2024.17,
  author =	{Banik, Aritra and Fomin, Fedor V. and Golovach, Petr A. and Inamdar, Tanmay and Jana, Satyabrata and Saurabh, Saket},
  title =	{{Cuts in Graphs with Matroid Constraints}},
  booktitle =	{32nd Annual European Symposium on Algorithms (ESA 2024)},
  pages =	{17:1--17:15},
  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.17},
  URN =		{urn:nbn:de:0030-drops-210887},
  doi =		{10.4230/LIPIcs.ESA.2024.17},
  annote =	{Keywords: s-t-cut, multiway Cut, matroid, odd cycle transversal, feedback vertex set, fixed-parameter tractability}
}
Document
DOI: 10.4230/LIPIcs.ESA.2024.25
Graph Spanners for Group Steiner Distances

Authors: Davide Bilò, Luciano Gualà, Stefano Leucci, and Alessandro Straziota

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

Abstract
A spanner is a sparse subgraph of a given graph G which preserves distances, measured w.r.t. some distance metric, up to a multiplicative stretch factor. This paper addresses the problem of constructing graph spanners w.r.t. the group Steiner metric, which generalizes the recently introduced beer distance metric. In such a metric we are given a collection of groups of required vertices, and we measure the distance between two vertices as the length of the shortest path between them that traverses at least one required vertex from each group. We discuss the relation between group Steiner spanners and classic spanners and we show that they exhibit strong ties with sourcewise spanners w.r.t. the shortest path metric. Nevertheless, group Steiner spanners capture several interesting scenarios that are not encompassed by existing spanners. This happens, e.g., for the singleton case, in which each group consists of a single required vertex, thus modeling the setting in which routes need to traverse certain points of interests (in any order). We provide several constructions of group Steiner spanners for both the all-pairs and single-source case, which exhibit various size-stretch trade-offs. Notably, we provide spanners with almost-optimal trade-offs for the singleton case. Moreover, some of our spanners also yield novel trade-offs for classical sourcewise spanners. Finally, we also investigate the query times that can be achieved when our spanners are turned into group Steiner distance oracles with the same size, stretch, and building time.
Cite as

Davide Bilò, Luciano Gualà, Stefano Leucci, and Alessandro Straziota. Graph Spanners for Group Steiner Distances. In 32nd Annual European Symposium on Algorithms (ESA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 308, pp. 25:1-25:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{bilo_et_al:LIPIcs.ESA.2024.25,
  author =	{Bil\`{o}, Davide and Gual\`{a}, Luciano and Leucci, Stefano and Straziota, Alessandro},
  title =	{{Graph Spanners for Group Steiner Distances}},
  booktitle =	{32nd Annual European Symposium on Algorithms (ESA 2024)},
  pages =	{25:1--25: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.25},
  URN =		{urn:nbn:de:0030-drops-210968},
  doi =		{10.4230/LIPIcs.ESA.2024.25},
  annote =	{Keywords: Network sparsification, Graph spanners, Group Steiner tree, Distance oracles}
}
Document
DOI: 10.4230/LIPIcs.ESA.2024.39
List Homomorphisms by Deleting Edges and Vertices: Tight Complexity Bounds for Bounded-Treewidth Graphs

Authors: Barış Can Esmer, Jacob Focke, Dániel Marx, and Paweł Rzążewski

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

Abstract
The goal of this paper is to investigate a family of optimization problems arising from list homomorphisms, and to understand what the best possible algorithms are if we restrict the problem to bounded-treewidth graphs. Given graphs G, H, and lists L(v) ⊆ V(H) for every v ∈ V(G), a list homomorphism from (G,L) to H is a function f:V(G) → V(H) that preserves the edges (i.e., uv ∈ E(G) implies f(u)f(v) ∈ E(H)) and respects the lists (i.e., f(v) ∈ L(v)). The graph H may have loops. For a fixed H, the input of the optimization problem LHomVD(H) is a graph G with lists L(v), and the task is to find a set X of vertices having minimum size such that (G-X,L) has a list homomorphism to H. We define analogously the edge-deletion variant LHomED(H), where we have to delete as few edges as possible from G to obtain a graph that has a list homomorphism. This expressive family of problems includes members that are essentially equivalent to fundamental problems such as Vertex Cover, Max Cut, Odd Cycle Transversal, and Edge/Vertex Multiway Cut. For both variants, we first characterize those graphs H that make the problem polynomial-time solvable and show that the problem is NP-hard for every other fixed H. Second, as our main result, we determine for every graph H for which the problem is NP-hard, the smallest possible constant c_H such that the problem can be solved in time c^t_H⋅ n^{𝒪(1)} if a tree decomposition of G having width t is given in the input. Let i(H) be the maximum size of a set of vertices in H that have pairwise incomparable neighborhoods. For the vertex-deletion variant LHomVD(H), we show that the smallest possible constant is i(H)+1 for every H: - Given a tree decomposition of width t of G, LHomVD(H) can be solved in time (i(H)+1)^t⋅ n^{𝒪(1)}. - For any ε > 0 and H, an (i(H)+1-ε)^t⋅ n^{𝒪(1)} algorithm would violate the Strong Exponential-Time Hypothesis (SETH). The situation is more complex for the edge-deletion version. For every H, one can solve LHomED(H) in time i(H)^t⋅ n^{𝒪(1)} if a tree decomposition of width t is given. However, the existence of a specific type of decomposition of H shows that there are graphs H where LHomED(H) can be solved significantly more efficiently and the best possible constant can be arbitrarily smaller than i(H). Nevertheless, we determine this best possible constant and (assuming the SETH) prove tight bounds for every fixed H.
Cite as

Barış Can Esmer, Jacob Focke, Dániel Marx, and Paweł Rzążewski. List Homomorphisms by Deleting Edges and Vertices: Tight Complexity Bounds for Bounded-Treewidth Graphs. In 32nd Annual European Symposium on Algorithms (ESA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 308, pp. 39:1-39:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{canesmer_et_al:LIPIcs.ESA.2024.39,
  author =	{Can Esmer, Bar{\i}\c{s} and Focke, Jacob and Marx, D\'{a}niel and Rz\k{a}\.{z}ewski, Pawe{\l}},
  title =	{{List Homomorphisms by Deleting Edges and Vertices: Tight Complexity Bounds for Bounded-Treewidth Graphs}},
  booktitle =	{32nd Annual European Symposium on Algorithms (ESA 2024)},
  pages =	{39:1--39:20},
  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.39},
  URN =		{urn:nbn:de:0030-drops-211103},
  doi =		{10.4230/LIPIcs.ESA.2024.39},
  annote =	{Keywords: Graph Homomorphism, List Homomorphism, Vertex Deletion, Edge Deletion, Multiway Cut, Parameterized Complexity, Tight Bounds, Treewidth, SETH}
}
Document
DOI: 10.4230/LIPIcs.ESA.2024.41
Approximation Algorithms for Hop Constrained and Buy-At-Bulk Network Design via Hop Constrained Oblivious Routing

Authors: Chandra Chekuri and Rhea Jain

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

Abstract
We consider two-cost network design models in which edges of the input graph have an associated cost and length. We build upon recent advances in hop-constrained oblivious routing to obtain two sets of results. We address multicommodity buy-at-bulk network design in the nonuniform setting. Existing poly-logarithmic approximations are based on the junction tree approach [Chekuri et al., 2010; Guy Kortsarz and Zeev Nutov, 2011]. We obtain a new polylogarithmic approximation via a natural LP relaxation. This establishes an upper bound on its integrality gap and affirmatively answers an open question raised in [Chekuri et al., 2010]. The rounding is based on recent results in hop-constrained oblivious routing [Ghaffari et al., 2021], and this technique yields a polylogarithmic approximation in more general settings such as set connectivity. Our algorithm for buy-at-bulk network design is based on an LP-based reduction to h-hop constrained network design for which we obtain LP-based bicriteria approximation algorithms. We also consider a fault-tolerant version of h-hop constrained network design where one wants to design a low-cost network to guarantee short paths between a given set of source-sink pairs even when k-1 edges can fail. This model has been considered in network design [Luis Gouveia and Markus Leitner, 2017; Gouveia et al., 2018; Arslan et al., 2020] but no approximation algorithms were known. We obtain polylogarithmic bicriteria approximation algorithms for the single-source setting for any fixed k. We build upon the single-source algorithm and the junction-tree approach to obtain an approximation algorithm for the multicommodity setting when at most one edge can fail.
Cite as

Chandra Chekuri and Rhea Jain. Approximation Algorithms for Hop Constrained and Buy-At-Bulk Network Design via Hop Constrained Oblivious Routing. In 32nd Annual European Symposium on Algorithms (ESA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 308, pp. 41:1-41:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{chekuri_et_al:LIPIcs.ESA.2024.41,
  author =	{Chekuri, Chandra and Jain, Rhea},
  title =	{{Approximation Algorithms for Hop Constrained and Buy-At-Bulk Network Design via Hop Constrained Oblivious Routing}},
  booktitle =	{32nd Annual European Symposium on Algorithms (ESA 2024)},
  pages =	{41:1--41:21},
  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.41},
  URN =		{urn:nbn:de:0030-drops-211124},
  doi =		{10.4230/LIPIcs.ESA.2024.41},
  annote =	{Keywords: Buy-at-bulk, Hop-constrained network design, LP integrality gap, Fault-tolerant network design}
}
Document
DOI: 10.4230/LIPIcs.ESA.2024.42
From Directed Steiner Tree to Directed Polymatroid Steiner Tree in Planar Graphs

Authors: Chandra Chekuri, Rhea Jain, Shubhang Kulkarni, Da Wei Zheng, and Weihao Zhu

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

Abstract
In the Directed Steiner Tree (DST) problem the input is a directed edge-weighted graph G = (V,E), a root vertex r and a set S ⊆ V of k terminals. The goal is to find a min-cost subgraph that connects r to each of the terminals. DST admits an O(log² k/log log k)-approximation in quasi-polynomial time [Grandoni et al., 2022; Rohan Ghuge and Viswanath Nagarajan, 2022], and an O(k^{ε})-approximation for any fixed ε > 0 in polynomial-time [Alexander Zelikovsky, 1997; Moses Charikar et al., 1999]. Resolving the existence of a polynomial-time poly-logarithmic approximation is a major open problem in approximation algorithms. In a recent work, Friggstad and Mousavi [Zachary Friggstad and Ramin Mousavi, 2023] obtained a simple and elegant polynomial-time O(log k)-approximation for DST in planar digraphs via Thorup’s shortest path separator theorem [Thorup, 2004]. We build on their work and obtain several new results on DST and related problems. - We develop a tree embedding technique for rooted problems in planar digraphs via an interpretation of the recursion in [Zachary Friggstad and Ramin Mousavi, 2023]. Using this we obtain polynomial-time poly-logarithmic approximations for Group Steiner Tree [Naveen Garg et al., 2000], Covering Steiner Tree [Goran Konjevod et al., 2002] and the Polymatroid Steiner Tree [Gruia Călinescu and Alexander Zelikovsky, 2005] problems in planar digraphs. All these problems are hard to approximate to within a factor of Ω(log² n/log log n) even in trees [Eran Halperin and Robert Krauthgamer, 2003; Grandoni et al., 2022]. - We prove that the natural cut-based LP relaxation for DST has an integrality gap of O(log² k) in planar digraphs. This is in contrast to general graphs where the integrality gap of this LP is known to be Ω(√k) [Leonid Zosin and Samir Khuller, 2002] and Ω(n^{δ}) for some fixed δ > 0 [Shi Li and Bundit Laekhanukit, 2022]. - We combine the preceding results with density based arguments to obtain poly-logarithmic approximations for the multi-rooted versions of the problems in planar digraphs. For DST our result improves the O(R + log k) approximation of [Zachary Friggstad and Ramin Mousavi, 2023] when R = ω(log² k).
Cite as

Chandra Chekuri, Rhea Jain, Shubhang Kulkarni, Da Wei Zheng, and Weihao Zhu. From Directed Steiner Tree to Directed Polymatroid Steiner Tree in Planar Graphs. In 32nd Annual European Symposium on Algorithms (ESA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 308, pp. 42:1-42:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{chekuri_et_al:LIPIcs.ESA.2024.42,
  author =	{Chekuri, Chandra and Jain, Rhea and Kulkarni, Shubhang and Zheng, Da Wei and Zhu, Weihao},
  title =	{{From Directed Steiner Tree to Directed Polymatroid Steiner Tree in Planar Graphs}},
  booktitle =	{32nd Annual European Symposium on Algorithms (ESA 2024)},
  pages =	{42:1--42:19},
  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.42},
  URN =		{urn:nbn:de:0030-drops-211134},
  doi =		{10.4230/LIPIcs.ESA.2024.42},
  annote =	{Keywords: Directed Planar Graphs, Submodular Functions, Steiner Tree, Network Design}
}
Document
DOI: 10.4230/LIPIcs.ESA.2024.43
Parameterized Approximation for Maximum Weight Independent Set of Rectangles and Segments

Authors: Jana Cslovjecsek, Michał Pilipczuk, and Karol Węgrzycki

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

Abstract
In the Maximum Weight Independent Set of Rectangles problem (MWISR) we are given a weighted set of n axis-parallel rectangles in the plane. The task is to find a subset of pairwise non-overlapping rectangles with the maximum possible total weight. This problem is NP-hard and the best-known polynomial-time approximation algorithm, due to Chalermsook and Walczak [SODA 2021], achieves approximation factor 𝒪(log log n). While in the unweighted setting, constant factor approximation algorithms are known, due to Mitchell [FOCS 2021] and to Gálvez et al. [SODA 2022], it remains open to extend these techniques to the weighted setting. In this paper, we consider MWISR through the lens of parameterized approximation. Grandoni, Kratsch and Wiese [ESA 2019] gave a (1-ε)-approximation algorithm running in k^{𝒪(k/ε⁸)} n^{𝒪(1/ε⁸)} time, where k is the number of rectangles in an optimum solution. Unfortunately, their algorithm works only in the unweighted setting and they left it as an open problem to give a parameterized approximation scheme in the weighted setting. We give a parameterized approximation algorithm for MWISR that given a parameter k ∈ ℕ, finds a set of non-overlapping rectangles of weight at least (1-ε) opt_k in 2^{𝒪(k log(k/ε))} n^{𝒪(1/ε)} time, where opt_k is the maximum weight of a solution of cardinality at most k. We also propose a parameterized approximation scheme with running time 2^{𝒪(k² log(k/ε))} n^{𝒪(1)} that finds a solution with cardinality at most k and total weight at least (1-ε)opt_k for the special case of axis-parallel segments.
Cite as

Jana Cslovjecsek, Michał Pilipczuk, and Karol Węgrzycki. Parameterized Approximation for Maximum Weight Independent Set of Rectangles and Segments. In 32nd Annual European Symposium on Algorithms (ESA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 308, pp. 43:1-43:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{cslovjecsek_et_al:LIPIcs.ESA.2024.43,
  author =	{Cslovjecsek, Jana and Pilipczuk, Micha{\l} and W\k{e}grzycki, Karol},
  title =	{{Parameterized Approximation for Maximum Weight Independent Set of Rectangles and Segments}},
  booktitle =	{32nd Annual European Symposium on Algorithms (ESA 2024)},
  pages =	{43:1--43:18},
  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.43},
  URN =		{urn:nbn:de:0030-drops-211146},
  doi =		{10.4230/LIPIcs.ESA.2024.43},
  annote =	{Keywords: parameterized approximation, Maximum Weight Independent Set, rectangles, segments}
}
Document
DOI: 10.4230/LIPIcs.ESA.2024.47
Bicriterial Approximation for the Incremental Prize-Collecting Steiner-Tree Problem

Authors: Yann Disser, Svenja M. Griesbach, Max Klimm, and Annette Lutz

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

Abstract
We consider an incremental variant of the rooted prize-collecting Steiner-tree problem with a growing budget constraint. While no incremental solution exists that simultaneously approximates the optimum for all budgets, we show that a bicriterial (α,μ)-approximation is possible, i.e., a solution that with budget B+α for all B ∈ ℝ_{≥ 0} is a multiplicative μ-approximation compared to the optimum solution with budget B. For the case that the underlying graph is a tree, we present a polynomial-time density-greedy algorithm that computes a (χ,1)-approximation, where χ denotes the eccentricity of the root vertex in the underlying graph, and show that this is best possible. An adaptation of the density-greedy algorithm for general graphs is (γ,2)-competitive where γ is the maximal length of a vertex-disjoint path starting in the root. While this algorithm does not run in polynomial time, it can be adapted to a (γ,3)-competitive algorithm that runs in polynomial time. We further devise a capacity-scaling algorithm that guarantees a (3χ,8)-approximation and, more generally, a ((4𝓁 - 1)χ, (2^{𝓁 + 2})/(2^𝓁 -1))-approximation for every fixed 𝓁 ∈ ℕ.
Cite as

Yann Disser, Svenja M. Griesbach, Max Klimm, and Annette Lutz. Bicriterial Approximation for the Incremental Prize-Collecting Steiner-Tree Problem. In 32nd Annual European Symposium on Algorithms (ESA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 308, pp. 47:1-47:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{disser_et_al:LIPIcs.ESA.2024.47,
  author =	{Disser, Yann and Griesbach, Svenja M. and Klimm, Max and Lutz, Annette},
  title =	{{Bicriterial Approximation for the Incremental Prize-Collecting Steiner-Tree Problem}},
  booktitle =	{32nd Annual European Symposium on Algorithms (ESA 2024)},
  pages =	{47:1--47:16},
  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.47},
  URN =		{urn:nbn:de:0030-drops-211188},
  doi =		{10.4230/LIPIcs.ESA.2024.47},
  annote =	{Keywords: incremental optimization, competitive analysis, prize-collecting Steiner-tree}
}
Document
DOI: 10.4230/LIPIcs.ESA.2024.57
Removing the log Factor from (min,+)-Products on Bounded Range Integer Matrices

Authors: Dvir Fried, Tsvi Kopelowitz, and Ely Porat

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

Abstract
We revisit the problem of multiplying two square matrices over the (min, +) semi-ring, where all entries are integers from a bounded range [-M : M] ∪ {∞}. The current state of the art for this problem is a simple O(M n^{ω} log M) time algorithm by Alon, Galil and Margalit [JCSS'97], where ω is the exponent in the runtime of the fastest matrix multiplication (FMM) algorithm. We design a new simple algorithm whose runtime is O(M n^ω + M n² log M), thereby removing the logM factor in the runtime if ω > 2 or if n^ω = Ω (n²log n).
Cite as

Dvir Fried, Tsvi Kopelowitz, and Ely Porat. Removing the log Factor from (min,+)-Products on Bounded Range Integer Matrices. In 32nd Annual European Symposium on Algorithms (ESA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 308, pp. 57:1-57:6, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{fried_et_al:LIPIcs.ESA.2024.57,
  author =	{Fried, Dvir and Kopelowitz, Tsvi and Porat, Ely},
  title =	{{Removing the log Factor from (min,+)-Products on Bounded Range Integer Matrices}},
  booktitle =	{32nd Annual European Symposium on Algorithms (ESA 2024)},
  pages =	{57:1--57:6},
  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.57},
  URN =		{urn:nbn:de:0030-drops-211283},
  doi =		{10.4230/LIPIcs.ESA.2024.57},
  annote =	{Keywords: FMM, (min , +)-product, FFT}
}
Document
DOI: 10.4230/LIPIcs.ESA.2024.58
Random-Order Online Independent Set of Intervals and Hyperrectangles

Authors: Mohit Garg, Debajyoti Kar, and Arindam Khan

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

Abstract
In the Maximum Independent Set of Hyperrectangles problem, we are given a set of n (possibly overlapping) d-dimensional axis-aligned hyperrectangles, and the goal is to find a subset of non-overlapping hyperrectangles of maximum cardinality. For d = 1, this corresponds to the classical Interval Scheduling problem, where a simple greedy algorithm returns an optimal solution. In the offline setting, for d-dimensional hyperrectangles, polynomial time (log n)^{O(d)}-approximation algorithms are known [Chalermsook and Chuzhoy, 2009]. However, the problem becomes notably challenging in the online setting, where the input objects (hyperrectangles) appear one by one in an adversarial order, and on the arrival of an object, the algorithm needs to make an immediate and irrevocable decision whether or not to select the object while maintaining the feasibility. Even for interval scheduling, an Ω(n) lower bound is known on the competitive ratio. To circumvent these negative results, in this work, we study the online maximum independent set of axis-aligned hyperrectangles in the random-order arrival model, where the adversary specifies the set of input objects which then arrive in a uniformly random order. Starting from the prototypical secretary problem, the random-order model has received significant attention to study algorithms beyond the worst-case competitive analysis (see the survey by Gupta and Singla [Anupam Gupta and Sahil Singla, 2020]). Surprisingly, we show that the problem in the random-order model almost matches the best-known offline approximation guarantees, up to polylogarithmic factors. In particular, we give a simple (log n)^{O(d)}-competitive algorithm for d-dimensional hyperrectangles in this model, which runs in O_d̃(n) time. Our approach also yields (log n)^{O(d)}-competitive algorithms in the random-order model for more general objects such as d-dimensional fat objects and ellipsoids. Furthermore, all our competitiveness guarantees hold with high probability, and not just in expectation.
Cite as

Mohit Garg, Debajyoti Kar, and Arindam Khan. Random-Order Online Independent Set of Intervals and Hyperrectangles. In 32nd Annual European Symposium on Algorithms (ESA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 308, pp. 58:1-58:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{garg_et_al:LIPIcs.ESA.2024.58,
  author =	{Garg, Mohit and Kar, Debajyoti and Khan, Arindam},
  title =	{{Random-Order Online Independent Set of Intervals and Hyperrectangles}},
  booktitle =	{32nd Annual European Symposium on Algorithms (ESA 2024)},
  pages =	{58:1--58:18},
  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.58},
  URN =		{urn:nbn:de:0030-drops-211298},
  doi =		{10.4230/LIPIcs.ESA.2024.58},
  annote =	{Keywords: Online Algorithms, Random-Order Model, Maximum Independent Set of Rectangles, Hyperrectangles, Fat Objects, Interval Scheduling}
}
Document
DOI: 10.4230/LIPIcs.ESA.2024.65
A Nearly Linear Time Construction of Approximate Single-Source Distance Sensitivity Oracles

Authors: Kaito Harada, Naoki Kitamura, Taisuke Izumi, and Toshimitsu Masuzawa

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

Abstract
An α-approximate vertex fault-tolerant distance sensitivity oracle (α-VSDO) for a weighted input graph G = (V, E, w) and a source vertex s ∈ V is the data structure answering an α-approximate distance from s to t in G-x for any given query (x, t) ∈ V × V. It is a data structure version of the so-called single-source replacement path problem (SSRP). In this paper, we present a new nearly linear-time algorithm of constructing a (1 + ε)-VSDO for any directed input graph with polynomially bounded integer edge weights. More precisely, the presented oracle attains Õ(m log (nW)/ ε + n log² (nW)/ε²) construction time, Õ(n log (nW) / ε) size, and Õ(1/ε) query time, where n is the number of vertices, m is the number of edges, and W is the maximum edge weight. These bounds are all optimal up to polylogarithmic factors. To the best of our knowledge, this is the first non-trivial algorithm for SSRP/VSDO beating Õ(mn) computation time for directed graphs with general edge weight functions, and also the first nearly linear-time construction breaking approximation factor 3. Such a construction has been unknown even for undirected and unweighted graphs. In addition, our result implies that the known conditional lower bounds for the exact SSRP computation does not apply to the case of approximation.
Cite as

Kaito Harada, Naoki Kitamura, Taisuke Izumi, and Toshimitsu Masuzawa. A Nearly Linear Time Construction of Approximate Single-Source Distance Sensitivity Oracles. In 32nd Annual European Symposium on Algorithms (ESA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 308, pp. 65:1-65:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{harada_et_al:LIPIcs.ESA.2024.65,
  author =	{Harada, Kaito and Kitamura, Naoki and Izumi, Taisuke and Masuzawa, Toshimitsu},
  title =	{{A Nearly Linear Time Construction of Approximate Single-Source Distance Sensitivity Oracles}},
  booktitle =	{32nd Annual European Symposium on Algorithms (ESA 2024)},
  pages =	{65:1--65:18},
  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.65},
  URN =		{urn:nbn:de:0030-drops-211367},
  doi =		{10.4230/LIPIcs.ESA.2024.65},
  annote =	{Keywords: data structure, distance sensitivity oracle, replacement path problem, graph algorithm}
}
Document
DOI: 10.4230/LIPIcs.ESA.2024.67
Approximation Algorithms for Steiner Connectivity Augmentation

Authors: Daniel Hathcock and Michael Zlatin

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

Abstract
We consider connectivity augmentation problems in the Steiner setting, where the goal is to augment the edge-connectivity between a specified subset of terminal nodes. In the Steiner Augmentation of a Graph problem (k-SAG), we are given a k-edge-connected subgraph H of a graph G. The goal is to augment H by including links from G of minimum cost so that the edge-connectivity between nodes of H increases by 1. This is a generalization of the Weighted Connectivity Augmentation Problem, in which only links between pairs of nodes in H are available for the augmentation. In the Steiner Connectivity Augmentation Problem (k-SCAP), we are given a Steiner k-edge-connected graph connecting terminals R, and we seek to add links of minimum cost to create a Steiner (k+1)-edge-connected graph for R. Note that k-SAG is a special case of k-SCAP. The results of Ravi, Zhang and Zlatin for the Steiner Tree Augmentation problem yield a (1.5+ε)-approximation for 1-SCAP and for k-SAG when k is odd [Ravi et al., 2023]. In this work, we give a (1 + ln{2} +ε)-approximation for the Steiner Ring Augmentation Problem (SRAP). This yields a polynomial time algorithm with approximation ratio (1 + ln{2} + ε) for 2-SCAP. We obtain an improved approximation guarantee for SRAP when the ring consists of only terminals, yielding a (1.5+ε)-approximation for k-SAG for any k.
Cite as

Daniel Hathcock and Michael Zlatin. Approximation Algorithms for Steiner Connectivity Augmentation. In 32nd Annual European Symposium on Algorithms (ESA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 308, pp. 67:1-67:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{hathcock_et_al:LIPIcs.ESA.2024.67,
  author =	{Hathcock, Daniel and Zlatin, Michael},
  title =	{{Approximation Algorithms for Steiner Connectivity Augmentation}},
  booktitle =	{32nd Annual European Symposium on Algorithms (ESA 2024)},
  pages =	{67:1--67:16},
  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.67},
  URN =		{urn:nbn:de:0030-drops-211387},
  doi =		{10.4230/LIPIcs.ESA.2024.67},
  annote =	{Keywords: Approximation Algorithms, Steiner Connectivity, Network Design}
}
Document
DOI: 10.4230/LIPIcs.ESA.2024.74
Improved Approximations for Flexible Network Design

Authors: Dylan Hyatt-Denesik, Afrouz Jabal-Ameli, and Laura Sanità

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

Abstract
Flexible network design deals with building a network that guarantees some connectivity requirements between its vertices, even when some of its elements (like vertices or edges) fail. In particular, the set of edges (resp. vertices) of a given graph are here partitioned into safe and unsafe. The goal is to identify a minimum size subgraph that is 2-edge-connected (resp. 2-vertex-connected), and stay so whenever any of the unsafe elements gets removed. In this paper, we provide improved approximation algorithms for flexible network design problems, considering both edge-connectivity and vertex-connectivity, as well as connectivity values higher than 2. For the vertex-connectivity variant, in particular, our algorithm is the first with approximation factor strictly better than 2.
Cite as

Dylan Hyatt-Denesik, Afrouz Jabal-Ameli, and Laura Sanità. Improved Approximations for Flexible Network Design. In 32nd Annual European Symposium on Algorithms (ESA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 308, pp. 74:1-74:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{hyattdenesik_et_al:LIPIcs.ESA.2024.74,
  author =	{Hyatt-Denesik, Dylan and Jabal-Ameli, Afrouz and Sanit\`{a}, Laura},
  title =	{{Improved Approximations for Flexible Network Design}},
  booktitle =	{32nd Annual European Symposium on Algorithms (ESA 2024)},
  pages =	{74:1--74:14},
  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.74},
  URN =		{urn:nbn:de:0030-drops-211456},
  doi =		{10.4230/LIPIcs.ESA.2024.74},
  annote =	{Keywords: Approximation Algorithms, Network Design, Flexible Connectivity}
}
Document
DOI: 10.4230/LIPIcs.ESA.2024.91
Euclidean Capacitated Vehicle Routing in the Random Setting: A 1.55-Approximation Algorithm

Authors: Zipei Nie and Hang Zhou

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

Abstract
We study the unit-demand capacitated vehicle routing problem in the random setting of the Euclidean plane. The objective is to visit n random terminals in a square using a set of tours of minimum total length, such that each tour visits the depot and at most k terminals. We design an algorithm combining the classical sweep heuristic and the framework for the Euclidean traveling salesman problem due to Arora [J. ACM 1998] and Mitchell [SICOMP 1999]. We show that our algorithm is a polynomial-time approximation of ratio at most 1.55 asymptotically almost surely. This improves on the prior ratio of 1.915 due to Mathieu and Zhou [RSA 2022]. In addition, we conjecture that, for any ε > 0, our algorithm is a (1+ε)-approximation asymptotically almost surely.
Cite as

Zipei Nie and Hang Zhou. Euclidean Capacitated Vehicle Routing in the Random Setting: A 1.55-Approximation Algorithm. In 32nd Annual European Symposium on Algorithms (ESA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 308, pp. 91:1-91:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{nie_et_al:LIPIcs.ESA.2024.91,
  author =	{Nie, Zipei and Zhou, Hang},
  title =	{{Euclidean Capacitated Vehicle Routing in the Random Setting: A 1.55-Approximation Algorithm}},
  booktitle =	{32nd Annual European Symposium on Algorithms (ESA 2024)},
  pages =	{91:1--91:15},
  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.91},
  URN =		{urn:nbn:de:0030-drops-211627},
  doi =		{10.4230/LIPIcs.ESA.2024.91},
  annote =	{Keywords: capacitated vehicle routing, approximation algorithm, combinatorial optimization}
}
  • Refine by Author
  • 19 Grandoni, Fabrizio
  • 6 Wiese, Andreas
  • 5 Fomin, Fedor V.
  • 5 Khan, Arindam
  • 5 Marx, Dániel
  • Show More...

  • Refine by Classification
  • 24 Mathematics of computing → Graph algorithms
  • 21 Theory of computation → Graph algorithms analysis
  • 21 Theory of computation → Parameterized complexity and exact algorithms
  • 20 Theory of computation → Approximation algorithms analysis
  • 19 Theory of computation → Design and analysis of algorithms
  • Show More...

  • Refine by Keyword
  • 9 Approximation Algorithms
  • 9 approximation algorithms
  • 6 Network Design
  • 5 approximation algorithm
  • 5 graph algorithms
  • Show More...

  • Refine by Type
  • 172 document
  • 2 volume

  • Refine by Publication Year
  • 87 2020
  • 46 2024
  • 29 2016
  • 3 2021
  • 2 2017
  • 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
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact