3 citations · 7 across the 13 of their papers we have counts for
10 papers · 1 filter
Optimizing Low Dimensional Functions over the Integers
Daniel Dadush, Arthur Léonard, Lars Rohwedder +1
We consider box-constrained integer programs with objective , where is a "complicated" function with an dimensional domain. Here we assume we have …
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…
A Primal-Dual Approximation Algorithm for Min-Sum Single-Machine Scheduling Problems
Maurice Cheung, Julián Mestre, David B. Shmoys +1
We consider the following single-machine scheduling problem, which is often denoted : we are given jobs to be scheduled on a single machine, where each job h…
Symmetry exploitation for Online Machine Covering with Bounded Migration
Waldo Gálvez, José A. Soto, José Verschae
Online models that allow recourse are highly effective in situations where classical models are too pessimistic. One such problem is the online machine covering problem on identica…
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…
A 4-approximation for scheduling on a single machine with general cost function
Julián Mestre, José Verschae
We consider a single machine scheduling problem that seeks to minimize a generalized cost function: given a subset of jobs we must order them so as to minimize , whe…
Dual techniques for scheduling on a machine with varying speed
Nicole Megow, José Verschae
We study scheduling problems on a machine with varying speed. Assuming a known speed function we ask for a cost-efficient scheduling solution. Our main result is a PTAS for minimiz…