Showing cs.DSShow all
3 papers · 1 filter
cs.DS2023
Node Connectivity Augmentation of Highly Connected Graphs
Waldo Galvez, Dylan Hyatt-Denesik, Afrouz Jabal Ameli +1
Node-connectivity augmentation is a fundamental network design problem. We are given a -node connected graph together with an additional set of links, and the goal is to add…
cs.DS2018
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…
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…