Max-Planck-Institut für Informatik
max planck institut
mpii logo Minerva of the Max Planck Society

MPI-INF or MPI-SWS or Local Campus Event Calendar

<< Previous Entry Next Entry >> New Event Entry Edit this Entry Login to DB (to update, delete)
What and Who
Title:Some Black-box Reductions for Cost-robust Discrete Optimization Problems
Speaker:Khaled Elbassioni
coming from:Khalifa University, UAE (former group member in D1)
Speakers Bio:
Event Type:AG1 Mittagsseminar (own work)
Visibility:D1, D3, D4, RG1, MMCI, D2, INET, D5, SWS
We use this to send out email in the morning.
Level:AG Audience
Date, Time and Location
Date:Friday, 21 June 2019
Duration:45 Minutes
Building:E1 4
Title: Some Black-box Reductions for Cost-robust Discrete Optimization Problems

Abstract: Standard optimization algorithms assume precise knowledge of their inputs, and find optimal or near-optimal solutions under this assumption. However, in real-life applications, the input data may be known up to a limited precision with errors introduced possibly due to inaccuracy in measurements or lack of exact information about the precise value of the input parameters. Clearly, an optimization algorithm designed based on such distorted data to optimize a certain objective function would not yield reliable results, if no special consideration of such uncertainty is taken. One of the basic approaches to deal with uncertainty in data is robust optimization, where some (deterministic) assumption is made on the uncertain parameters, and the objective is to optimize over the worst-case these parameters can assume.

In this talk, we consider robust discrete optimization problems with cost uncertainty defined by a convex set. Assuming the existence of an integrality gap verifier with a bounded approximation guarantee for the LP relaxation of the non-robust version of the problem, we derive approximation algorithms for the robust version under different types of uncertainty, including polyhedral and ellipsoidal uncertainty

Name(s):Kurt Mehlhorn
Video Broadcast
Video Broadcast:NoTo Location:
Tags, Category, Keywords and additional notes
Attachments, File(s):
  • Kurt Mehlhorn, 06/18/2019 02:46 PM
  • Kurt Mehlhorn, 06/07/2019 02:24 PM -- Created document.