TITLE: Computing with Uncertainty
SPEAKER: Thomas Erlebach (The University of Leicester)
ABSTRACT:
We consider problems where the input data is initially
uncertain but the exact value of an input item can be obtained at a
certain cost. For example, a typical setting is that instead of an
exact value, only an interval containing the exact value is given. An
update of an input item then reveals its exact value. This scenario
models real-world situations where only estimates of some input
parameters are known initially, but it is possible to obtain the
actual values of the input parameters with some extra effort. An
algorithm performs a number of updates until it has gathered
sufficient information to output a correct solution to the
problem. The goal is to minimise the number of updates.
We discuss several problems in the setting of computing with
uncertainty, including the minimum spanning tree problem and the
minimum multicut problem in trees. Algorithms are evaluated using
competitive analysis, comparing the number of updates that the
algorithm makes on an instance of the problem to the best possible
number of updates that suffices to solve that instance.
(The talk is based on joint work with Michael Hoffmann, Frank Kammer, Danny
Krizanc, Matus Mihalak, and Rajeev Raman.)