131 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.2023.17
Approximating Min-Diameter: Standard and Bichromatic

Authors: Aaron Berger, Jenny Kaufmann, and Virginia Vassilevska Williams

Published in: LIPIcs, Volume 274, 31st Annual European Symposium on Algorithms (ESA 2023)

Abstract
The min-diameter of a directed graph G is a measure of the largest distance between nodes. It is equal to the maximum min-distance d_{min}(u,v) across all pairs u,v ∈ V(G), where d_{min}(u,v) = min(d(u,v), d(v,u)). Min-diameter approximation in directed graphs has attracted attention recently as an offshoot of the classical and well-studied diameter approximation problem. Our work provides a 3/2-approximation algorithm for min-diameter in DAGs running in time O(m^{1.426} n^{0.288}), and a faster almost-3/2-approximation variant which runs in time O(m^{0.713} n). (An almost-α-approximation algorithm determines the min-diameter to within a multiplicative factor of α plus constant additive error.) This is the first known algorithm to solve 3/2-approximation for min-diameter in sparse DAGs in truly subquadratic time O(m^{2-ε}) for ε > 0; previously only a 2-approximation was known. By a conditional lower bound result of [Abboud et al, SODA 2016], a better than 3/2-approximation can't be achieved in truly subquadratic time under the Strong Exponential Time Hypothesis (SETH), so our result is conditionally tight. We additionally obtain a new conditional lower bound for min-diameter approximation in general directed graphs, showing that under SETH, one cannot achieve an approximation factor below 2 in truly subquadratic time. Our work also presents the first study of approximating bichromatic min-diameter, which is the maximum min-distance between oppositely colored vertices in a 2-colored graph. We show that SETH implies that in DAGs, a better than 2 approximation cannot be achieved in truly subquadratic time, and that in general graphs, an approximation within a factor below 5/2 is similarly out of reach. We then obtain an O(m)-time algorithm which determines if bichromatic min-diameter is finite, and an almost-2-approximation algorithm for bichromatic min-diameter with runtime Õ(min(m^{4/3} n^{1/3}, m^{1/2} n^{3/2})).
Cite as

Aaron Berger, Jenny Kaufmann, and Virginia Vassilevska Williams. Approximating Min-Diameter: Standard and Bichromatic. In 31st Annual European Symposium on Algorithms (ESA 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 274, pp. 17:1-17:14, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{berger_et_al:LIPIcs.ESA.2023.17,
  author =	{Berger, Aaron and Kaufmann, Jenny and Vassilevska Williams, Virginia},
  title =	{{Approximating Min-Diameter: Standard and Bichromatic}},
  booktitle =	{31st Annual European Symposium on Algorithms (ESA 2023)},
  pages =	{17:1--17:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-295-2},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{274},
  editor =	{G{\o}rtz, Inge Li and Farach-Colton, Martin and Puglisi, Simon J. 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.2023.17},
  URN =		{urn:nbn:de:0030-drops-186705},
  doi =		{10.4230/LIPIcs.ESA.2023.17},
  annote =	{Keywords: diameter, min distances, fine-grained, approximation algorithm}
}
Document
DOI: 10.4230/LIPIcs.SEA.2023.6
Proxying Betweenness Centrality Rankings in Temporal Networks

Authors: Ruben Becker, Pierluigi Crescenzi, Antonio Cruciani, and Bojana Kodric

Published in: LIPIcs, Volume 265, 21st International Symposium on Experimental Algorithms (SEA 2023)

Abstract
Identifying influential nodes in a network is arguably one of the most important tasks in graph mining and network analysis. A large variety of centrality measures, all aiming at correctly quantifying a node’s importance in the network, have been formulated in the literature. One of the most cited ones is the betweenness centrality, formally introduced by Freeman (Sociometry, 1977). On the other hand, researchers have recently been very interested in capturing the dynamic nature of real-world networks by studying temporal graphs, rather than static ones. Clearly, centrality measures, including the betweenness centrality, have also been extended to temporal graphs. Buß et al. (KDD, 2020) gave algorithms to compute various notions of temporal betweenness centrality, including the perhaps most natural one - shortest temporal betweenness. Their algorithm computes centrality values of all nodes in time O(n³ T²), where n is the size of the network and T is the total number of time steps. For real-world networks, which easily contain tens of thousands of nodes, this complexity becomes prohibitive. Thus, it is reasonable to consider proxies for shortest temporal betweenness rankings that are more efficiently computed, and, therefore, allow for measuring the relative importance of nodes in very large temporal graphs. In this paper, we compare several such proxies on a diverse set of real-world networks. These proxies can be divided into global and local proxies. The considered global proxies include the exact algorithm for static betweenness (computed on the underlying graph), prefix foremost temporal betweenness of Buß et al., which is more efficiently computable than shortest temporal betweenness, and the recently introduced approximation approach of Santoro and Sarpe (WWW, 2022). As all of these global proxies are still expensive to compute on very large networks, we also turn to more efficiently computable local proxies. Here, we consider temporal versions of the ego-betweenness in the sense of Everett and Borgatti (Social Networks, 2005), standard degree notions, and a novel temporal degree notion termed the pass-through degree, that we introduce in this paper and which we consider to be one of our main contributions. We show that the pass-through degree, which measures the number of pairs of neighbors of a node that are temporally connected through it, can be computed in nearly linear time for all nodes in the network and we experimentally observe that it is surprisingly competitive as a proxy for shortest temporal betweenness.
Cite as

Ruben Becker, Pierluigi Crescenzi, Antonio Cruciani, and Bojana Kodric. Proxying Betweenness Centrality Rankings in Temporal Networks. In 21st International Symposium on Experimental Algorithms (SEA 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 265, pp. 6:1-6:22, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{becker_et_al:LIPIcs.SEA.2023.6,
  author =	{Becker, Ruben and Crescenzi, Pierluigi and Cruciani, Antonio and Kodric, Bojana},
  title =	{{Proxying Betweenness Centrality Rankings in Temporal Networks}},
  booktitle =	{21st International Symposium on Experimental Algorithms (SEA 2023)},
  pages =	{6:1--6:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-279-2},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{265},
  editor =	{Georgiadis, Loukas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2023.6},
  URN =		{urn:nbn:de:0030-drops-183568},
  doi =		{10.4230/LIPIcs.SEA.2023.6},
  annote =	{Keywords: node centrality, betweenness, temporal graphs, graph mining}
}
Document
DOI: 10.4230/LIPIcs.SEA.2023.10
Solving Directed Feedback Vertex Set by Iterative Reduction to Vertex Cover

Authors: Sebastian Angrick, Ben Bals, Katrin Casel, Sarel Cohen, Tobias Friedrich, Niko Hastrich, Theresa Hradilak, Davis Issac, Otto Kißig, Jonas Schmidt, and Leo Wendt

Published in: LIPIcs, Volume 265, 21st International Symposium on Experimental Algorithms (SEA 2023)

Abstract
In the Directed Feedback Vertex Set (DFVS) problem, one is given a directed graph G = (V,E) and wants to find a minimum cardinality set S ⊆ V such that G-S is acyclic. DFVS is a fundamental problem in computer science and finds applications in areas such as deadlock detection. The problem was the subject of the 2022 PACE coding challenge. We develop a novel exact algorithm for the problem that is tailored to perform well on instances that are mostly bi-directed. For such instances, we adapt techniques from the well-researched vertex cover problem. Our core idea is an iterative reduction to vertex cover. To this end, we also develop a new reduction rule that reduces the number of not bi-directed edges. With the resulting algorithm, we were able to win third place in the exact track of the PACE challenge. We perform computational experiments and compare the running time to other exact algorithms, in particular to the winning algorithm in PACE. Our experiments show that we outpace the other algorithms on instances that have a low density of uni-directed edges.
Cite as

Sebastian Angrick, Ben Bals, Katrin Casel, Sarel Cohen, Tobias Friedrich, Niko Hastrich, Theresa Hradilak, Davis Issac, Otto Kißig, Jonas Schmidt, and Leo Wendt. Solving Directed Feedback Vertex Set by Iterative Reduction to Vertex Cover. In 21st International Symposium on Experimental Algorithms (SEA 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 265, pp. 10:1-10:14, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{angrick_et_al:LIPIcs.SEA.2023.10,
  author =	{Angrick, Sebastian and Bals, Ben and Casel, Katrin and Cohen, Sarel and Friedrich, Tobias and Hastrich, Niko and Hradilak, Theresa and Issac, Davis and Ki{\ss}ig, Otto and Schmidt, Jonas and Wendt, Leo},
  title =	{{Solving Directed Feedback Vertex Set by Iterative Reduction to Vertex Cover}},
  booktitle =	{21st International Symposium on Experimental Algorithms (SEA 2023)},
  pages =	{10:1--10:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-279-2},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{265},
  editor =	{Georgiadis, Loukas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2023.10},
  URN =		{urn:nbn:de:0030-drops-183602},
  doi =		{10.4230/LIPIcs.SEA.2023.10},
  annote =	{Keywords: directed feedback vertex set, vertex cover, reduction rules}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2023.29
A 4/3 Approximation for 2-Vertex-Connectivity

Authors: Miguel Bosch-Calvo, Fabrizio Grandoni, and Afrouz Jabal Ameli

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

Abstract
The 2-Vertex-Connected Spanning Subgraph problem (2VCSS) is among the most basic NP-hard (Survivable) Network Design problems: we are given an (unweighted) undirected graph G. Our goal is to find a subgraph S of G with the minimum number of edges which is 2-vertex-connected, namely S remains connected after the deletion of an arbitrary node. 2VCSS is well-studied in terms of approximation algorithms, and the current best (polynomial-time) approximation factor is 10/7 by Heeger and Vygen [SIDMA'17] (improving on earlier results by Khuller and Vishkin [STOC'92] and Garg, Vempala and Singla [SODA'93]). Here we present an improved 4/3 approximation. Our main technical ingredient is an approximation preserving reduction to a conveniently structured subset of instances which are "almost" 3-vertex-connected. The latter reduction might be helpful in future work.
Cite as

Miguel Bosch-Calvo, Fabrizio Grandoni, and Afrouz Jabal Ameli. A 4/3 Approximation for 2-Vertex-Connectivity. In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 261, pp. 29:1-29:13, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{boschcalvo_et_al:LIPIcs.ICALP.2023.29,
  author =	{Bosch-Calvo, Miguel and Grandoni, Fabrizio and Jabal Ameli, Afrouz},
  title =	{{A 4/3 Approximation for 2-Vertex-Connectivity}},
  booktitle =	{50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)},
  pages =	{29:1--29:13},
  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.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2023.29},
  URN =		{urn:nbn:de:0030-drops-180813},
  doi =		{10.4230/LIPIcs.ICALP.2023.29},
  annote =	{Keywords: Algorithm, Network Design, Vertex-Connectivity, Approximation}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2023.63
Unsplittable Euclidean Capacitated Vehicle Routing: A (2+ε)-Approximation Algorithm

Authors: Fabrizio Grandoni, Claire Mathieu, and Hang Zhou

Published in: LIPIcs, Volume 251, 14th Innovations in Theoretical Computer Science Conference (ITCS 2023)

Abstract
In the unsplittable capacitated vehicle routing problem, we are given a metric space with a vertex called depot and a set of vertices called terminals. Each terminal is associated with a positive demand between 0 and 1. The goal is to find a minimum length collection of tours starting and ending at the depot such that the demand of each terminal is covered by a single tour (i.e., the demand cannot be split), and the total demand of the terminals in each tour does not exceed the capacity of 1. Our main result is a polynomial-time (2+ε)-approximation algorithm for this problem in the two-dimensional Euclidean plane, i.e., for the special case where the terminals and the depot are associated with points in the Euclidean plane and their distances are defined accordingly. This improves on recent work by Blauth, Traub, and Vygen [IPCO'21] and Friggstad, Mousavi, Rahgoshay, and Salavatipour [IPCO'22].
Cite as

Fabrizio Grandoni, Claire Mathieu, and Hang Zhou. Unsplittable Euclidean Capacitated Vehicle Routing: A (2+ε)-Approximation Algorithm. In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 251, pp. 63:1-63:13, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{grandoni_et_al:LIPIcs.ITCS.2023.63,
  author =	{Grandoni, Fabrizio and Mathieu, Claire and Zhou, Hang},
  title =	{{Unsplittable Euclidean Capacitated Vehicle Routing: A (2+\epsilon)-Approximation Algorithm}},
  booktitle =	{14th Innovations in Theoretical Computer Science Conference (ITCS 2023)},
  pages =	{63:1--63:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-263-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{251},
  editor =	{Tauman Kalai, Yael},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2023.63},
  URN =		{urn:nbn:de:0030-drops-175660},
  doi =		{10.4230/LIPIcs.ITCS.2023.63},
  annote =	{Keywords: capacitated vehicle routing, approximation algorithms, Euclidean plane}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2022.11
Decremental Matching in General Graphs

Authors: Sepehr Assadi, Aaron Bernstein, and Aditi Dudeja

Published in: LIPIcs, Volume 229, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)

Abstract
We consider the problem of maintaining an approximate maximum integral matching in a dynamic graph G, while the adversary makes changes to the edges of the graph. The goal is to maintain a (1+ε)-approximate maximum matching for constant ε > 0, while minimizing the update time. In the fully dynamic setting, where both edge insertion and deletions are allowed, Gupta and Peng (see [Manoj Gupta and Richard Peng, 2013]) gave an algorithm for this problem with an update time of O(√m/ε²). Motivated by the fact that the O_ε(√m) barrier is hard to overcome (see Henzinger, Krinninger, Nanongkai, and Saranurak [Henzinger et al., 2015]; Kopelowitz, Pettie, and Porat [Kopelowitz et al., 2016]), we study this problem in the decremental model, where the adversary is only allowed to delete edges. Recently, Bernstein, Probst-Gutenberg, and Saranurak (see [Bernstein et al., 2020]) gave an O(poly({log n}/ε)) update time decremental algorithm for this problem in bipartite graphs. However, beating O(√m) update time remained an open problem for general graphs. In this paper, we bridge the gap between bipartite and general graphs, by giving an O_ε(poly(log n)) update time algorithm that maintains a (1+ε)-approximate maximum integral matching under adversarial deletions. Our algorithm is randomized, but works against an adaptive adversary. Together with the work of Grandoni, Leonardi, Sankowski, Schwiegelshohn, and Solomon [Fabrizio Grandoni et al., 2019] who give an O_ε(1) update time algorithm for general graphs in the incremental (insertion-only) model, our result essentially completes the picture for partially dynamic matching.
Cite as

Sepehr Assadi, Aaron Bernstein, and Aditi Dudeja. Decremental Matching in General Graphs. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, pp. 11:1-11:19, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{assadi_et_al:LIPIcs.ICALP.2022.11,
  author =	{Assadi, Sepehr and Bernstein, Aaron and Dudeja, Aditi},
  title =	{{Decremental Matching in General Graphs}},
  booktitle =	{49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)},
  pages =	{11:1--11:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-235-8},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{229},
  editor =	{Boja\'{n}czyk, Miko{\l}aj and Merelli, Emanuela and Woodruff, David P.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2022.11},
  URN =		{urn:nbn:de:0030-drops-163528},
  doi =		{10.4230/LIPIcs.ICALP.2022.11},
  annote =	{Keywords: Dynamic algorithms, matching, primal-dual algorithms}
}
Document
APPROX
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2021.20
Approximation Algorithms for Demand Strip Packing

Authors: Waldo Gálvez, Fabrizio Grandoni, Afrouz Jabal Ameli, and Kamyar Khodamoradi

Published in: LIPIcs, Volume 207, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021)

Abstract
In the Demand Strip Packing problem (DSP), we are given a time interval and a collection of tasks, each characterized by a processing time and a demand for a given resource (such as electricity, computational power, etc.). A feasible solution consists of a schedule of the tasks within the mentioned time interval. Our goal is to minimize the peak resource consumption, i.e. the maximum total demand of tasks executed at any point in time. It is known that DSP is NP-hard to approximate below a factor 3/2, and standard techniques for related problems imply a (polynomial-time) 2-approximation. Our main result is a (5/3+ε)-approximation algorithm for any constant ε > 0. We also achieve best-possible approximation factors for some relevant special cases.
Cite as

Waldo Gálvez, Fabrizio Grandoni, Afrouz Jabal Ameli, and Kamyar Khodamoradi. Approximation Algorithms for Demand Strip Packing. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 207, pp. 20:1-20:24, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{galvez_et_al:LIPIcs.APPROX/RANDOM.2021.20,
  author =	{G\'{a}lvez, Waldo and Grandoni, Fabrizio and Ameli, Afrouz Jabal and Khodamoradi, Kamyar},
  title =	{{Approximation Algorithms for Demand Strip Packing}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021)},
  pages =	{20:1--20:24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-207-5},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{207},
  editor =	{Wootters, Mary and Sanit\`{a}, Laura},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2021.20},
  URN =		{urn:nbn:de:0030-drops-147130},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2021.20},
  annote =	{Keywords: Strip Packing, Two-Dimensional Packing, Approximation Algorithms}
}
Document
DOI: 10.4230/LIPIcs.ESA.2021.49
Faster (1+ε)-Approximation for Unsplittable Flow on a Path via Resource Augmentation and Back

Authors: Fabrizio Grandoni, Tobias Mömke, and Andreas Wiese

Published in: LIPIcs, Volume 204, 29th Annual European Symposium on Algorithms (ESA 2021)

Abstract
Unsplittable flow on a path (UFP) is an important and well-studied problem. We are given a path with capacities on its edges, and a set of tasks where for each task we are given a demand, a subpath, and a weight. The goal is to select the set of tasks of maximum total weight whose total demands do not exceed the capacity on any edge. UFP admits an (1+ε)-approximation with a running time of n^{O_{ε}(poly(log n))}, i.e., a QPTAS {[}Bansal et al., STOC 2006; Batra et al., SODA 2015{]} and it is considered an important open problem to construct a PTAS. To this end, in a series of papers polynomial time approximation algorithms have been developed, which culminated in a (5/3+ε)-approximation {[}Grandoni et al., STOC 2018{]} and very recently an approximation ratio of (1+1/(e+1)+ε) < 1.269 {[}Grandoni et al., 2020{]}. In this paper, we address the search for a PTAS from a different angle: we present a faster (1+ε)-approximation with a running time of only n^{O_{ε}(log log n)}. We first give such a result in the relaxed setting of resource augmentation and then transform it to an algorithm without resource augmentation. For this, we present a framework which transforms algorithms for (a slight generalization of) UFP under resource augmentation in a black-box manner into algorithms for UFP without resource augmentation, with only negligible loss.
Cite as

Fabrizio Grandoni, Tobias Mömke, and Andreas Wiese. Faster (1+ε)-Approximation for Unsplittable Flow on a Path via Resource Augmentation and Back. In 29th Annual European Symposium on Algorithms (ESA 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 204, pp. 49:1-49:15, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{grandoni_et_al:LIPIcs.ESA.2021.49,
  author =	{Grandoni, Fabrizio and M\"{o}mke, Tobias and Wiese, Andreas},
  title =	{{Faster (1+\epsilon)-Approximation for Unsplittable Flow on a Path via Resource Augmentation and Back}},
  booktitle =	{29th Annual European Symposium on Algorithms (ESA 2021)},
  pages =	{49:1--49:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-204-4},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{204},
  editor =	{Mutzel, Petra and Pagh, Rasmus 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.2021.49},
  URN =		{urn:nbn:de:0030-drops-146301},
  doi =		{10.4230/LIPIcs.ESA.2021.49},
  annote =	{Keywords: Approximation Algorithms, Unsplittable Flow, Dynamic Programming}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2021.39
Improved Approximation Algorithms for 2-Dimensional Knapsack: Packing into Multiple L-Shapes, Spirals, and More

Authors: Waldo Gálvez, Fabrizio Grandoni, Arindam Khan, Diego Ramírez-Romero, and Andreas Wiese

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

Abstract
In the 2-Dimensional Knapsack problem (2DK) we are given a square knapsack and a collection of n rectangular items with integer sizes and profits. Our goal is to find the most profitable subset of items that can be packed non-overlappingly into the knapsack. The currently best known polynomial-time approximation factor for 2DK is 17/9+ε < 1.89 and there is a (3/2+ε)-approximation algorithm if we are allowed to rotate items by 90 degrees [Gálvez et al., FOCS 2017]. In this paper, we give (4/3+ε)-approximation algorithms in polynomial time for both cases, assuming that all input data are integers polynomially bounded in n. Gálvez et al.’s algorithm for 2DK partitions the knapsack into a constant number of rectangular regions plus one L-shaped region and packs items into those in a structured way. We generalize this approach by allowing up to a constant number of more general regions that can have the shape of an L, a U, a Z, a spiral, and more, and therefore obtain an improved approximation ratio. In particular, we present an algorithm that computes the essentially optimal structured packing into these regions.
Cite as

Waldo Gálvez, Fabrizio Grandoni, Arindam Khan, Diego Ramírez-Romero, and Andreas Wiese. Improved Approximation Algorithms for 2-Dimensional Knapsack: Packing into Multiple L-Shapes, Spirals, and More. In 37th International Symposium on Computational Geometry (SoCG 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 189, pp. 39:1-39:17, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{galvez_et_al:LIPIcs.SoCG.2021.39,
  author =	{G\'{a}lvez, Waldo and Grandoni, Fabrizio and Khan, Arindam and Ram{\'\i}rez-Romero, Diego and Wiese, Andreas},
  title =	{{Improved Approximation Algorithms for 2-Dimensional Knapsack: Packing into Multiple L-Shapes, Spirals, and More}},
  booktitle =	{37th International Symposium on Computational Geometry (SoCG 2021)},
  pages =	{39:1--39:17},
  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.39},
  URN =		{urn:nbn:de:0030-drops-138386},
  doi =		{10.4230/LIPIcs.SoCG.2021.39},
  annote =	{Keywords: Approximation algorithms, two-dimensional knapsack, geometric packing}
}
Document
Complete Volume
DOI: 10.4230/LIPIcs.ESA.2020
LIPIcs, Volume 173, ESA 2020, Complete Volume

Authors: Fabrizio Grandoni, Grzegorz Herman, and Peter Sanders

Published in: LIPIcs, Volume 173, 28th Annual European Symposium on Algorithms (ESA 2020)

Abstract
LIPIcs, Volume 173, ESA 2020, Complete Volume
Cite as

Fabrizio Grandoni, Grzegorz Herman, and Peter Sanders. LIPIcs, Volume 173, ESA 2020, Complete Volume. In 28th Annual European Symposium on Algorithms (ESA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 173, pp. 1-1598, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@Proceedings{grandoni_et_al:LIPIcs.ESA.2020,
  title =	{{LIPIcs, Volume 173, ESA 2020, Complete Volume}},
  booktitle =	{28th Annual European Symposium on Algorithms (ESA 2020)},
  pages =	{1--1598},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-162-7},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{173},
  editor =	{Grandoni, Fabrizio and Herman, Grzegorz and Sanders, Peter},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2020},
  URN =		{urn:nbn:de:0030-drops-128651},
  doi =		{10.4230/LIPIcs.ESA.2020},
  annote =	{Keywords: LIPIcs, Volume 173, ESA 2020, Complete Volume}
}
Document
Front Matter
DOI: 10.4230/LIPIcs.ESA.2020.0
Front Matter, Table of Contents, Preface, Conference Organization

Authors: Fabrizio Grandoni, Grzegorz Herman, and Peter Sanders

Published in: LIPIcs, Volume 173, 28th Annual European Symposium on Algorithms (ESA 2020)

Abstract
Front Matter, Table of Contents, Preface, Conference Organization
Cite as

Fabrizio Grandoni, Grzegorz Herman, and Peter Sanders. Front Matter, Table of Contents, Preface, Conference Organization. In 28th Annual European Symposium on Algorithms (ESA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 173, pp. 0:i-0:xx, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{grandoni_et_al:LIPIcs.ESA.2020.0,
  author =	{Grandoni, Fabrizio and Herman, Grzegorz and Sanders, Peter},
  title =	{{Front Matter, Table of Contents, Preface, Conference Organization}},
  booktitle =	{28th Annual European Symposium on Algorithms (ESA 2020)},
  pages =	{0:i--0:xx},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-162-7},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{173},
  editor =	{Grandoni, Fabrizio and Herman, Grzegorz and Sanders, Peter},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2020.0},
  URN =		{urn:nbn:de:0030-drops-128669},
  doi =		{10.4230/LIPIcs.ESA.2020.0},
  annote =	{Keywords: Front Matter, Table of Contents, Preface, Conference Organization}
}
Document
DOI: 10.4230/LIPIcs.ESA.2020.1
Planar Bichromatic Bottleneck Spanning Trees

Authors: A. Karim Abu-Affash, Sujoy Bhore, Paz Carmi, and Joseph S. B. Mitchell

Published in: LIPIcs, Volume 173, 28th Annual European Symposium on Algorithms (ESA 2020)

Abstract
Given a set P of n red and blue points in the plane, a planar bichromatic spanning tree of P is a geometric spanning tree of P, such that each edge connects between a red and a blue point, and no two edges intersect. In the bottleneck planar bichromatic spanning tree problem, the goal is to find a planar bichromatic spanning tree T, such that the length of the longest edge in T is minimized. In this paper, we show that this problem is NP-hard for points in general position. Our main contribution is a polynomial-time (8√2)-approximation algorithm, by showing that any bichromatic spanning tree of bottleneck λ can be converted to a planar bichromatic spanning tree of bottleneck at most 8√2 λ.
Cite as

A. Karim Abu-Affash, Sujoy Bhore, Paz Carmi, and Joseph S. B. Mitchell. Planar Bichromatic Bottleneck Spanning Trees. In 28th Annual European Symposium on Algorithms (ESA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 173, pp. 1:1-1:16, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{abuaffash_et_al:LIPIcs.ESA.2020.1,
  author =	{Abu-Affash, A. Karim and Bhore, Sujoy and Carmi, Paz and Mitchell, Joseph S. B.},
  title =	{{Planar Bichromatic Bottleneck Spanning Trees}},
  booktitle =	{28th Annual European Symposium on Algorithms (ESA 2020)},
  pages =	{1:1--1:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-162-7},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{173},
  editor =	{Grandoni, Fabrizio and Herman, Grzegorz and Sanders, Peter},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2020.1},
  URN =		{urn:nbn:de:0030-drops-128670},
  doi =		{10.4230/LIPIcs.ESA.2020.1},
  annote =	{Keywords: Approximation Algorithms, Bottleneck Spanning Tree, NP-Hardness}
}
Document
DOI: 10.4230/LIPIcs.ESA.2020.2
Parallel Batch-Dynamic Trees via Change Propagation

Authors: Umut A. Acar, Daniel Anderson, Guy E. Blelloch, Laxman Dhulipala, and Sam Westrick

Published in: LIPIcs, Volume 173, 28th Annual European Symposium on Algorithms (ESA 2020)

Abstract
The dynamic trees problem is to maintain a forest subject to edge insertions and deletions while facilitating queries such as connectivity, path weights, and subtree weights. Dynamic trees are a fundamental building block of a large number of graph algorithms. Although traditionally studied in the single-update setting, dynamic algorithms capable of supporting batches of updates are increasingly relevant today due to the emergence of rapidly evolving dynamic datasets. Since processing updates on a single processor is often unrealistic for large batches of updates, designing parallel batch-dynamic algorithms that achieve provably low span is important for many applications. In this work, we design the first work-efficient parallel batch-dynamic algorithm for dynamic trees that is capable of supporting both path queries and subtree queries, as well as a variety of nonlocal queries. Previous work-efficient dynamic trees of Tseng et al. were only capable of handling subtree queries [ALENEX'19, (2019), pp. 92 - 106]. To achieve this, we propose a framework for algorithmically dynamizing static round-synchronous algorithms to obtain parallel batch-dynamic algorithms. In our framework, the algorithm designer can apply the technique to any suitably defined static algorithm. We then obtain theoretical guarantees for algorithms in our framework by defining the notion of a computation distance between two executions of the underlying algorithm. Our dynamic trees algorithm is obtained by applying our dynamization framework to the parallel tree contraction algorithm of Miller and Reif [FOCS'85, (1985), pp. 478 - 489], and then performing a novel analysis of the computation distance of this algorithm under batch updates. We show that k updates can be performed in O(klog(1+n/k)) work in expectation, which matches the algorithm of Tseng et al. while providing support for a substantially larger number of queries and applications.
Cite as

Umut A. Acar, Daniel Anderson, Guy E. Blelloch, Laxman Dhulipala, and Sam Westrick. Parallel Batch-Dynamic Trees via Change Propagation. In 28th Annual European Symposium on Algorithms (ESA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 173, pp. 2:1-2:23, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{acar_et_al:LIPIcs.ESA.2020.2,
  author =	{Acar, Umut A. and Anderson, Daniel and Blelloch, Guy E. and Dhulipala, Laxman and Westrick, Sam},
  title =	{{Parallel Batch-Dynamic Trees via Change Propagation}},
  booktitle =	{28th Annual European Symposium on Algorithms (ESA 2020)},
  pages =	{2:1--2:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-162-7},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{173},
  editor =	{Grandoni, Fabrizio and Herman, Grzegorz and Sanders, Peter},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2020.2},
  URN =		{urn:nbn:de:0030-drops-128686},
  doi =		{10.4230/LIPIcs.ESA.2020.2},
  annote =	{Keywords: Dynamic trees, Graph algorithms, Parallel algorithms, Dynamic algorithms}
}
  • Refine by Author
  • 17 Grandoni, Fabrizio
  • 5 Wiese, Andreas
  • 4 Demaine, Erik D.
  • 4 Fomin, Fedor V.
  • 4 Gálvez, Waldo
  • Show More...

  • Refine by Classification
  • 19 Mathematics of computing → Graph algorithms
  • 16 Theory of computation → Computational geometry
  • 15 Theory of computation → Graph algorithms analysis
  • 14 Theory of computation → Design and analysis of algorithms
  • 14 Theory of computation → Parameterized complexity and exact algorithms
  • Show More...

  • Refine by Keyword
  • 7 approximation algorithms
  • 5 Approximation Algorithms
  • 5 approximation algorithm
  • 4 kernelization
  • 3 Approximation
  • Show More...

  • Refine by Type
  • 129 document
  • 2 volume

  • Refine by Publication Year
  • 87 2020
  • 29 2016
  • 5 2023
  • 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 Schloss Dagstuhl - LZI GmbH Imprint Privacy Contact