21 citations · 89 across the 29 of their papers we have counts for
Showing 2017 · cs.DSShow all
3 papers · 2 filters
cs.DS2017
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…
cs.DS2017
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…
cs.DS2017★ 4 cited
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…