# Fabrizio Grandoni

According to our database1, Fabrizio Grandoni authored at least 110 papers between 2003 and 2021.

Collaborative distances:
• Dijkstra number2 of four.
• Erdős number3 of two.

Book
In proceedings
Article
PhD thesis
Other

## Bibliography

2021
Improved Approximation Algorithms for 2-Dimensional Knapsack: Packing into Multiple L-Shapes, Spirals, and More.
CoRR, 2021

All-Pairs LCA in DAGs: Breaking through the <i>O</i>(<i>n</i><sup>2.5</sup>) barrier.
Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, 2021

Online Edge Coloring Algorithms via the Nibble Method.
Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, 2021

2020
Faster Replacement Paths and Distance Sensitivity Oracles.
ACM Trans. Algorithms, 2020

The matching augmentation problem: a $\frac{7}{4}$-approximation algorithm.
Math. Program., 2020

Improved Approximation Algorithms for Stochastic-Matching Problems.
CoRR, 2020

All-Pairs LCA in DAGs: Breaking through the O(n<sup>2.5</sup>) barrier.
CoRR, 2020

Breaching the 2-approximation barrier for connectivity augmentation: a reduction to Steiner tree.
Proceedings of the Proccedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, 2020

A Tight (3/2+ε) Approximation for Skewed Strip Packing.
Proceedings of the Approximation, 2020

2019
Truly Subcubic Algorithms for Language Edit Distance and RNA Folding via Fast Bounded-Difference Min-Plus Product.
SIAM J. Comput., 2019

Fully Dynamic (Δ+1)-Coloring in Constant Update Time.
CoRR, 2019

On the Cycle Augmentation Problem: Hardness and Approximation Algorithms.
Proceedings of the Approximation and Online Algorithms - 17th International Workshop, 2019

Oblivious dimension reduction for <i>k</i>-means: beyond subspaces and the Johnson-Lindenstrauss lemma.
Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, 2019

Dynamic set cover: improved algorithms and lower bounds.
Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, 2019

<i>O</i>(log<sup>2</sup> <i>k</i> / log log <i>k</i>)-approximation algorithm for directed Steiner tree: a tight quasi-polynomial-time algorithm.
Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, 2019

(1 + ε)-Approximate Incremental Matching in Constant Deterministic Amortized Time.
Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2019

Packing Cars into Narrow Roads: PTASs for Limited Supply Highway.
Proceedings of the 27th Annual European Symposium on Algorithms, 2019

Parameterized Approximation Schemes for Independent Set of Rectangles and Geometric Knapsack.
Proceedings of the 27th Annual European Symposium on Algorithms, 2019

2018
Editorial fun.
Theor. Comput. Sci., 2018

Editorial: ACM-SIAM Symposium on Discrete Algorithms (SODA) 2016 Special Issue.
ACM Trans. Algorithms, 2018

A Mazing 2+ϵ Approximation for Unsplittable Flow on a Path.
ACM Trans. Algorithms, 2018

O(log<sup>2</sup>k/log log k)-Approximation Algorithm for Directed Steiner Tree: A Tight Quasi-Polynomial-Time Algorithm.
CoRR, 2018

The Matching Augmentation Problem: A 7/4-Approximation Algorithm.
CoRR, 2018

A (5/3 + ε)-approximation for unsplittable flow on a path: placing small tasks into boxes.
Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, 2018

Improved approximation for tree augmentation: saving by rewiring.
Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, 2018

Distributed Approximation Algorithms via LP-Duality and Randomization.
Proceedings of the Handbook of Approximation Algorithms and Metaheuristics, 2018

2017
Tight Kernel Bounds for Problems on Graphs with Small Degeneracy.
ACM Trans. Algorithms, 2017

Surviving in directed graphs: a quasi-polynomial-time polylogarithmic approximation for two-connected directed Steiner tree.
Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, 2017

To Augment or Not to Augment: Solving Unsplittable Flow on a Path by Creating Slack.
Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 2017

Preserving Distances in Very Faulty Graphs.
Proceedings of the 44th International Colloquium on Automata, Languages, and Programming, 2017

When the Optimum is also Blind: a New Perspective on Universal Optimization.
Proceedings of the 44th International Colloquium on Automata, Languages, and Programming, 2017

Approximating Geometric Knapsack via L-Packings.
Proceedings of the 58th IEEE Annual Symposium on Foundations of Computer Science, 2017

2016
Exact Algorithms for Maximum Independent Set.
Encyclopedia of Algorithms, 2016

Pricing on Paths: A PTAS for the Highway Problem.
SIAM J. Comput., 2016

Surviving in Directed Graphs: A Polylogarithmic Approximation for Two-Connected Directed Steiner Tree.
CoRR, 2016

Online Network Design with Outliers.
Algorithmica, 2016

Improved Pseudo-Polynomial-Time Approximation for Strip Packing.
Proceedings of the 36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2016

Truly Sub-cubic Algorithms for Language Edit Distance and RNA-Folding via Fast Bounded-Difference Min-Plus Product.
Proceedings of the IEEE 57th Annual Symposium on Foundations of Computer Science, 2016

2015
An LP-rounding 2√2-approximation for restricted maximum acyclic subgraph.
Inf. Process. Lett., 2015

Improved Approximation Algorithms for Unsplittable Flow on a Path with Time Windows.
Proceedings of the Approximation and Online Algorithms - 13th International Workshop, 2015

On Conflict-Free Multi-coloring.
Proceedings of the Algorithms and Data Structures - 14th International Symposium, 2015

On Survivable Set Connectivity.
Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, 2015

Subcubic Equivalences Between Graph Centrality Problems, APSP and Diameter.
Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, 2015

Proceedings of the Algorithms - ESA 2015, 2015

Improved Approximation Algorithms for Stochastic Matching.
Proceedings of the Algorithms - ESA 2015, 2015

2014
Utilitarian Mechanism Design for Multiobjective Optimization.
SIAM J. Comput., 2014

New approaches to multi-objective optimization.
Math. Program., 2014

An LP-Rounding $2\sqrt{2}$ Approximation for Restricted Maximum Acyclic Subgraph.
CoRR, 2014

A Mazing 2+<i>∊</i> Approximation for Unsplittable Flow on a Path.
Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, 2014

2013
Set Covering with Our Eyes Closed.
SIAM J. Comput., 2013

Data structures resilient to memory faults: An experimental study of dictionaries.
ACM J. Exp. Algorithmics, 2013

Steiner Tree Approximation via Iterative Randomized Rounding.
J. ACM, 2013

Computing Optimal Steiner Trees in Polynomial Space.
Algorithmica, 2013

On Pairwise Spanners.
Proceedings of the 30th International Symposium on Theoretical Aspects of Computer Science, 2013

How to Sell Hyperedges: The Hypermatching Assignment Problem.
Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, 2013

Constant Integrality Gap LP Formulations of Unsplittable Flow on a Path.
Proceedings of the Integer Programming and Combinatorial Optimization, 2013

Tight Kernel Bounds for Problems on Graphs with Small Degeneracy - (Extended Abstract).
Proceedings of the Algorithms - ESA 2013, 2013

2012
A Mazing 2+eps Approximation for Unsplittable Flow on a Path
CoRR, 2012

Sharp Separation and Applications to Exact and Parameterized Algorithms.
Algorithmica, 2012

Improved Distance Sensitivity Oracles via Fast Single-Source Replacement Paths.
Proceedings of the 53rd Annual IEEE Symposium on Foundations of Computer Science, 2012

On Min-Power Steiner Tree.
Proceedings of the Algorithms - ESA 2012, 2012

A Path-Decomposition Theorem with Applications to Pricing and Covering on Trees.
Proceedings of the Algorithms - ESA 2012, 2012

2011
Budgeted matching and budgeted matroid intersection via the gasoline puzzle.
Math. Program., 2011

From Uncertainty to Nonlinearity: Solving Virtual Private Network via Single-Sink Buy-at-Bulk.
Math. Oper. Res., 2011

Approximation Algorithms for Single and Multi-Commodity Connected Facility Location.
Proceedings of the Integer Programming and Combinatoral Optimization, 2011

Approximation Algorithms for Union and Intersection Covering Problems.
Proceedings of the IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2011

2010
Stable routing under the Spanning Tree Protocol.
Oper. Res. Lett., 2010

Connected facility location via random facility sampling and core detouring.
J. Comput. Syst. Sci., 2010

Prizing on Paths: A PTAS for the Highway Problem
CoRR, 2010

Optimization with More than One Budget
CoRR, 2010

An improved LP-based approximation for steiner tree.
Proceedings of the 42nd ACM Symposium on Theory of Computing, 2010

Utilitarian Mechanism Design for Multi-Objective Optimization.
Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, 2010

Network Design via Core Detouring for Problems without a Core.
Proceedings of the Automata, Languages and Programming, 37th International Colloquium, 2010

Approximation Schemes for Multi-Budgeted Independence Systems.
Proceedings of the Algorithms, 2010

2009
Optimal resilient sorting and searching in the presence of memory faults.
Theor. Comput. Sci., 2009

Balanced cut approximation in random geometric graphs.
Theor. Comput. Sci., 2009

Resilient dictionaries.
ACM Trans. Algorithms, 2009

A measure & conquer approach for the analysis of exact algorithms.
J. ACM, 2009

Iterative Rounding for Multi-Objective Optimization Problems.
Proceedings of the Algorithms, 2009

2008
Exact Algorithms for Dominating Set.
Proceedings of the Encyclopedia of Algorithms - 2008 Edition, 2008

Distributed weighted vertex cover via maximal matchings.
ACM Trans. Algorithms, 2008

Combinatorial bounds via measure and conquer: Bounding minimal dominating sets and applications.
ACM Trans. Algorithms, 2008

A Primal-Dual Bicriteria Distributed Algorithm for Capacitated Vertex Cover.
SIAM J. Comput., 2008

A short proof of the VPN Tree Routing Conjecture on ring networks.
Oper. Res. Lett., 2008

Solving Connected Dominating Set Faster than 2<sup> <i>n</i> </sup>.
Algorithmica, 2008

Approximating connected facility location problems via random facility sampling and core detouring.
Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2008

Faster Steiner Tree Computation in Polynomial-Space.
Proceedings of the Algorithms, 2008

2007
Distributed Approximation Algorithms via LP-Duality and Randomization.
Proceedings of the Handbook of Approximation Algorithms and Metaheuristics., 2007

New Approaches for Virtual Private Network Design.
SIAM J. Comput., 2007

Designing reliable algorithms in unreliable memories.
Comput. Sci. Rev., 2007

Resilient search trees.
Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2007

Fast Low Degree Connectivity of Ad-Hoc Networks Via Percolation.
Proceedings of the Algorithms, 2007

Optimal Resilient Dynamic Dictionaries.
Proceedings of the Algorithms, 2007

2006
A note on the complexity of minimum dominating set.
J. Discrete Algorithms, 2006

A linear time algorithm to list the minimal separators of chordal graphs.
Discret. Math., 2006

Measure and conquer: a simple O(2<sup>0.288<i>n</i></sup>) independent set algorithm.
Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2006

Proceedings of the Algorithms and Computation, 17th International Symposium, 2006

Algorithms and Constraint Programming.
Proceedings of the Principles and Practice of Constraint Programming, 2006

2005
Refined memorization for vertex cover.
Inf. Process. Lett., 2005

On maximum number of minimal dominating sets in graphs.
Electron. Notes Discret. Math., 2005

Some New Techniques in Design and Analysis of Exact (Exponential) Algorithms.
Bull. EATCS, 2005

An improved approximation algorithm for virtual private network design.
Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2005

Primal-dual based distributed algorithms for vertex cover with semi-hard capacities.
Proceedings of the Twenty-Fourth Annual ACM Symposium on Principles of Distributed Computing, 2005

Bounding the Number of Minimal Dominating Sets: A Measure and Conquer Approach.
Proceedings of the Algorithms and Computation, 16th International Symposium, 2005

Measure and Conquer: Domination - A Case Study.
Proceedings of the Automata, Languages and Programming, 32nd International Colloquium, 2005

2004
On the complexity of fixed parameter clique and dominating set.
Theor. Comput. Sci., 2004

Decremental Clique Problem.
Proceedings of the Graph-Theoretic Concepts in Computer Science, 2004

Refined Memorisation for Vertex Cover.
Proceedings of the Parameterized and Exact Computation, First International Workshop, 2004

2003
Detecting directed 4-cycles still faster.
Inf. Process. Lett., 2003

Improved Algorithms for Max-restricted Path Consistency.
Proceedings of the Principles and Practice of Constraint Programming, 2003