Christoph Dürr. Centre National de la Recherche Scientifique (Cnrs); Centro de Modelamiento Matemático (Cmm), Universidad de Chile
Three problems under explorable uncertainty
Presencial en Auditorio Edificio San Agustín. Opción vía Zoom: https://us06web.zoom.us/j/88006820878?pwd=aCtnM0QvMlFYK3BjdWU5VWRQbzRXdz09 (Código: MtEQ0c)
Abstract:
If you have ever worked on an industrial project you might have noticed that it is really difficult to obtain the input data for the problem you are supposed to solve. At the best you obtain some estimations. This situation motivated the study of a computational model, where the input is given only in an imprecise form, in the sense that every variable is drawn from a known distribution with finite support. You have the possibility to make queries in order to learn the exact values. The goal is to make as few queries as possible in order to solve the problem. In this talk we will consider the problem of sorting a set of variables, of determining the minimum among a set of variables, and more generally of determining the minimum among several overlapping sets of variables.
This talk will cover results from the following papers:
Orienting (hyper)graphs under explorable stochastic uncertainty. Evripidis Bampis, Christoph Dürr, Thomas Erlebach, Murilo S. de Lima, Nicole Megow and Jens Schlöter. European Symposium on Algorithms (ESA), 2021.
Query minimization under stochastic uncertainty. Steven Chaplick, Magnús M. Halldórsson, Murilo S. de Lima and Tigran Tonoyan. Latin American Theoretical Informatics Symposium (LATIN) 2020.