 |
Universität Augsburg
|
|
|
Universität Augsburg
|
|
Herr Émile Naquin
Université de Bordeaux
spricht am
Dienstag, 3. Februar 2026
um
14:00 Uhr
im
Raum 3008 (L1)
über das Thema:
| Abstract: |
| When modeling real-life problems, more often than not the data are imprecise, which means that some property of robustness is desirable in optimization algorithms. We study the case where the weights of a linear minimization problem are each known to be contained in some interval, the bounds of which are known. The goal is to find a solution of minimal regret, that is, which is as close as possible to the optimum in the worst-case possible weight. While Kasperski found a simple general approximation algorithm more than 15 years ago, it was restricted to polynomial-time problems which become NP-hard when considered in the robust setting. It was only five years ago that Ganesh, Maggs and Panigrahi showed that the robust versions TSP and Steiner Tree could also be approximated in polynomial time. We discuss their results, and present some new results, notably an extension to other problems admitting a local search algorithm satisfying some properties, and in the case where the lower bound of all of the intervals is 0. |
| Hierzu ergeht herzliche Einladung. |
| Prof. Dr. Mirjam Dür |