21 citations · 89 across the 29 of their papers we have counts for
5 papers · 1 filter
-Approximation Algorithm for Directed Steiner Tree: A Tight Quasi-Polynomial-Time Algorithm
Fabrizio Grandoni, Bundit Laekhanukit, Shi Li
In the Directed Steiner Tree (DST) problem we are given an -vertex directed edge-weighted graph, a root , and a collection of terminal nodes. Our goal is to find a minimu…
The Matching Augmentation Problem: A -Approximation Algorithm
Joe Cheriyan, Jack Dippel, Fabrizio Grandoni +2
We present a approximation algorithm for the matching augmentation problem (MAP): given a multi-graph with edges of cost either zero or one such that the edges of cost ze…
Improved Approximation for Tree Augmentation: Saving by Rewiring
Fabrizio Grandoni, Christos Kalaitzis, Rico Zenklusen
The Tree Augmentation Problem (TAP) is a fundamental network design problem in which we are given a tree and a set of additional edges, also called \emph{links}. The task is to fin…
Dynamic Set Cover: Improved Algorithms & Lower Bounds
Amir Abboud, Raghavendra Addanki, Fabrizio Grandoni +2
We give new upper and lower bounds for the {\em dynamic} set cover problem. First, we give a -approximation for fully dynamic set cover in (amortized)…
Improved Pseudo-Polynomial-Time Approximation for Strip Packing
Waldo Gálvez, Fabrizio Grandoni, Salvatore Ingala +1
We study the strip packing problem, a classical packing problem which generalizes both bin packing and makespan minimization. Here we are given a set of axis-parallel rectangles in…