Showing cs.DSShow all
3 papers · 1 filter
cs.DS2021
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…
cs.DS2021
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…
cs.DS2021
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…