21 citations · 89 across the 29 of their papers we have counts for
4 papers · 1 filter
Approximating Geometric Knapsack via L-packings
Waldo Gálvez, Fabrizio Grandoni, Sandy Heydrich +3
We study the two-dimensional geometric knapsack problem (2DK) in which we are given a set of n axis-aligned rectangular items, each one with an associated profit, and an axis-align…
Truly Sub-cubic Algorithms for Language Edit Distance and RNA Folding via Fast Bounded-Difference Min-Plus Product
Karl Bringmann, Fabrizio Grandoni, Barna Saha +1
It is a major open problem whether the -product of two matrices has a truly sub-cubic (i.e. for ) time algorithm, in particular since it is…
When the Optimum is also Blind: a New Perspective on Universal Optimization
Marek Adamczyk, Fabrizio Grandoni, Stefano Leonardi +1
Consider the following variant of the set cover problem. We are given a universe and a collection of subsets where …
Preserving Distances in Very Faulty Graphs
Greg Bodwin, Fabrizio Grandoni, Merav Parter +1
Preservers and additive spanners are sparse (hence cheap to store) subgraphs that preserve the distances between given pairs of nodes exactly or with some small additive error, res…