Universal and Robust Optimization

In robust optimization we are still dealing with uncertainty in the problem input, but are given a selection of scenarios that might occur. Our goal is to find solutions for the underlying problem that satisfy some performance guarantees or constraints for every given scenario. In contrast to online optimization, algorithms for robust optimization are often non-adaptive. That is, we ask for a single solution that performs well on any given scenario.

As an example consider the speed-robust scheduling problem. In this problem, we have to group given jobs into bags which afterwards have to be assigned to machines for processing. However, the processing speeds of the machines are initially unknown and only revealed after the bags are already fixed, and after the bags are fixed all jobs of a bag have to be assigned to the same machine. The goal is to find a grouping of the jobs that can be efficiently scheduled for every possible configuration of speeds (compared to the respective optimal schedules that can be computed with upfront knowledge of the speeds). As part of the project, we designed several algorithms for the general speed-robust scheduling problem and some special cases.

Street sign illustrating the different scenarios in robust optimization

Speed-Robust Scheduling: Sand, Bricks, and Rocks
Franziska Eberle, Ruben Hoeksma, Nicole Megow, Lukas Nölke, Kevin Schewior, Bertrand Simon
Mathematical Programming (accepted)

Speed-Robust Scheduling arxiv.org
Franziska Eberle, Ruben Hoeksma, Nicole Megow, Lukas Nölke, Kevin Schewior, Bertrand Simon IPCO
2021

Packing a Knapsack of Unknown Capacity PDF
Y. Disser, M. Klimm, N. Megow, S. Stiller
SIAM Journal on Discrete Mathematics 31(3): 1477-1497, 2017.

Universal Sequencing on an Unreliable Machine
N. Megow, Julian Mestre
Encyclopedia of Algorithms 2016: 2304-2308.

Stochastic and Robust Scheduling in the Cloud PDF
L. Chen, N. Megow, R. Rischke and L. Stougie
In Proc. of the 18th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX 2015), LIPIcs 40, pp. 175-186, 2015.

Packing a Knapsack of Unknown Capacity PDF
Y. Disser, M. Klimm, N. Megow, S. Stiller
In Proc. of the 31st Symposium on Theoretical Aspects of Computer Science (STACS 2015), pp. 276-287, 2015

Robustness and Approximation for Universal Sequencing
Gems of Combinatorial Optimization and Graph Algorithms 2015: 133-141.

Instance-sensitive robustness guarantees for sequencing with unknown packing and covering constraints PDF
N. Megow, J. Mestre
In Proc. of the 4th Conference on Innovations in Theoretical Computer Science (ITCS 2013), pp. 495-504, 2013.

Universal sequencing on a single unreliable machine PDF
L. Epstein, A. Levin, N. Megow, J. Mestre, A. Marchetti-Spaccamela, M. Skutella, L Stougie
SIAM Journal on Computing, Vol. 41, pp. 565-586, 2012.

Updated by: Lukas Barning

RSS

Print page

Universal and Robust Optimization

Publications on Universal and Robust Optimization