Séminaire

Date : 5 mars 2026 14:00 - Salle :Amphi 3 - Pôle commun Set Selection with Uncertain Weights: Non-Adaptative Queries and Thresholds Christoph Dürr, CNRS DR - LIP6 Paris

For illustration, suppose we have to compute a shortest path in a graph between two vertices, but the edge weights are uncertain. All we know is that the weight $w_e$ of every edge $e$ belongs to some interval $[ell_e, h_e]$.  In this setting, for every fixed edge $e$, we can define two thresholds $T_e^+, T_e^-$ such that $e$ belongs to every shortest path if $w_e < T_e^+$ and to none if $w_e > T_e^-$. We study the problem of computing these thresholds, for various set selection problems. In particular we show that the problem is easy for the minimum spanning tree problem and the maximum weight matching problem on trees. In contrast we show that the problem is NP-hard for the shortest path problem and for the minimum cost perfect matching problem.
This is joint work with Arturo Merino, José A. Soto and José Verschae.

https://www.lip6.fr/Christoph.Durr/