View publication
| Title | Set Selection with Uncertain Weights: Non-Adaptive Queries and Thresholds |
| Authors | Cristoph Dürr, Arturo Merino, José Soto, José Verschae |
| Publication date | 2026 |
| Abstract | 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 \lt T_e^+ and to none if w_e \gt 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. |
| Pages | 281-295 |
| Conference name | International Workshop on Combinatorial Algorithms |
| Reference URL |
|