21 citations · 89 across the 29 of their papers we have counts for
5 papers · 1 filter
Breaching the 2-Approximation Barrier for the Forest Augmentation Problem
Fabrizio Grandoni, Afrouz Jabal Ameli, Vera Traub
The basic goal of survivable network design is to build cheap networks that guarantee the connectivity of certain pairs of nodes despite the failure of a few edges or nodes. A cele…
Maintaining an EDCS in General Graphs: Simpler, Density-Sensitive and with Worst-Case Time Bounds
Fabrizio Grandoni, Chris Schwiegelshohn, Shay Solomon +1
In their breakthrough ICALP'15 paper, Bernstein and Stein presented an algorithm for maintaining a -approximate maximum matching in fully dynamic {\em bipartite} graphs wi…
A Refined Approximation for Euclidean k-Means
Fabrizio Grandoni, Rafail Ostrovsky, Yuval Rabani +2
In the Euclidean -Means problem we are given a collection of points in an Euclidean space and a positive integer . Our goal is to identify a collection of points…
Approximation Algorithms for Demand Strip Packing
Waldo Gálvez, Fabrizio Grandoni, Afrouz Jabal Ameli +1
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 a…
Improved Approximation Algorithms for 2-Dimensional Knapsack: Packing into Multiple L-Shapes, Spirals, and More
Waldo Gálvez, Fabrizio Grandoni, Arindam Khan +2
In the \textsc{2-Dimensional Knapsack} problem (2DK) we are given a square knapsack and a collection of rectangular items with integer sizes and profits. Our goal is to find th…