Project
AA3-19
The Value of Distributional Information
Project Heads
Franziska Eberle
Project Members
N.N.
Project Duration
01.09.2024 – 31.08.2027
Located at
TU Berlin
Description
This project studies the dependency between the amount of available distributional information and the approximability of optimal solutions in combinatorial optimization problems. We quantify how much distributional information should be available to the decision maker in order to find near-optimal solutions.
A prerequisite for classic optimization is the assumption that all problem parameters are known in advance and remain fixed. However, uncertainty is a prevalent and challenging facet of many real-world decision environments. This motivates the study of optimization under uncertainty, where decisions must be made given only incomplete information about the input. Two prominent variants of optimization under uncertainty are stochastic and robust optimization. In stochastic optimization the uncertain problem parameters U are modeled as (often independent) random variables and the decision maker is assumed to have full access to their joint distribution. In this setting, the decision maker is interested in optimizing some objective function in expectation. However, in many applications, the assumption that the distribution is precisely known is overly optimistic, as, e.g., historical data might be misrepresenting the current situation. In contrast, in robust optimization the uncertainty is represented by a set of scenarios, and the goal is to hedge against the worst-case scenario. That is, after seeing the decision maker’s solution, a malicious adversary selects the scenario which causes the worst possible objective function value. In real-life situations, this model might be overly pessimistic as the worst-case scenario might happen with negligible probability. Distributionally robust optimization nicely interpolates between these two models by assuming that the uncertain problem parameters U follow a joint, but unknown distribution to which the decision maker has limited access, e.g., only the first and second moments of U are known.
For several NP-hard optimization problems such as load balancing or congestion minimization, we want to design approximation algorithms with parameterized access to distributional information. More precisely, we are interested in quantifying how much distributional information an algorithm needs in order to recover the state-of-the-art of approximation with oracle, or full, access to the distribution. Ideally, we obtain approximation guarantees with smooth dependency on the amount of available distributional information.
Project Webpages
Related Publications
- M. Buchem, F. Eberle, H.K. Kasuya Rosado, K. Schewior, and A. Wiese. Scheduling on a Stochastic Number of Machines. Accepted for presentation at APPROX 2024.
Selected Pictures
Please insert any kind of pictures (photos, diagramms, simulations, graphics) related to the project in the above right field (Image with Text), by choosing the green plus image on top of the text editor. (You will be directed to the media library where you can add new files.)
(We need pictures for a lot of purposes in different contexts, like posters, scientific reports, flyers, website,…
Please upload pictures that might be just nice to look at, illustrate, explain or summarize your work.)
As Title in the above form please add a copyright.
And please give a short description of the picture and the context in the above textbox.
Don’t forget to press the “Save changes” button at the bottom of the box.
If you want to add more pictures, please use the “clone”-button at the right top of the above grey box.