2 citations · 2 across the 4 of their papers we have counts for
5 papers · 1 filter
A Water-Filling Primal-Dual Algorithm for Approximating Non-Linear Covering Problems
Andrés Fielbaum, Ignacio Morales, José Verschae
Obtaining strong linear relaxations of capacitated covering problems constitute a major technical challenge even for simple settings. For one of the most basic cases, the Knapsack-…
Optimal Algorithms for Scheduling under Time-of-Use Tariffs
Lin Chen, Nicole Megow, Roman Rischke +2
We consider a natural generalization of classical scheduling problems in which using a time unit for processing a job causes some time-dependent cost which must be paid in addition…
Breaking symmetries to rescue Sum of Squares in the case of makespan scheduling
Victor Verdugo, José Verschae, Andreas Wiese
The Sum of Squares (\sos{}) hierarchy gives an automatized technique to create a family of increasingly tight convex relaxations for binary programs. There are several problems for…
A Local-Search Algorithm for Steiner Forest
Martin Groß, Anupam Gupta, Amit Kumar +4
In the Steiner Forest problem, we are given a graph and a collection of source-sink pairs, and the goal is to find a subgraph of minimum total length such that all pairs are connec…
Closing the Gap for Makespan Scheduling via Sparsification Techniques
Klaus Jansen, Kim-Manuel Klein, José Verschae
Makespan scheduling on identical machines is one of the most basic and fundamental packing problems studied in the discrete optimization literature. It asks for an assignment of $n…