5 papers
Approximation Algorithms for Vertex-Connectivity Augmentation on the Cycle
Waldo Gálvez, Francisco Sanhueza-Matamala, José A. Soto
Given a -vertex-connected graph and a set of extra edges (links), the goal of the -vertex-connectivity augmentation problem is to find a set of minim…
Machine Covering in the Random-Order Model
Susanne Albers, Waldo Gálvez, Maximilian Janke
In the Online Machine Covering problem jobs, defined by their sizes, arrive one by one and have to be assigned to parallel and identical machines, with the goal of maximizing t…
A (2+ε)-Approximation Algorithm for Maximum Independent Set of Rectangles
Waldo Gálvez, Arindam Khan, Mathieu Mari +3
We study the Maximum Independent Set of Rectangles (MISR) problem, where we are given a set of axis-parallel rectangles in the plane and the goal is to select a subset of non-overl…
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…