Seminar: Algorithms for Queryable Uncertainty



Professor Thomas Erlebach
Department of Computer Science, University of Leicester, UK


Queryable uncertainty refers to settings where the input of a problem is initially not known precisely, but exact information about the input can be obtained at a cost using queries. A natural goal is then to minimize the number of the queries that are required until the precise information that has been obtained about the input is sufficient for solving the problem. The performance of an algorithm can be measured using competitive analysis, comparing the number of queries made by the algorithm to the minimum possible number of queries. We describe the witness set algorithm concept and how it yields query-competitive algorithms for minimum spanning tree and cheapest set problems under uncertainty. We also discuss the problem
variant where the algorithm can make a bounded number of simultaneous queries in each round and the goal is to minimize the number of rounds.