Monday, April 15, 2013
Humboldt-Universität zu Berlin
Institut für Informatik
Rudower Chaussee 25
12489 Berlin
Humboldt-Kabinett
Lecture - 14:15
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. 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.)
Colloquium - 16:00
Abstract:
Network Creation Games attempt to model the creation and evolution of
complex networks, which are build in a decentralized way by selfish
agents. Each selfish agent tries to balance the two contradicting
objectives of maximizing the quality of network usage and minimizing the
number of (costly) links that have to be created and maintained to
connect to the network. Clearly, the Internet is a prominent example of
such a network and it can be considered as an equilibrium state of a
Network Creation Game. Here, the agents are Internet Service Providers
and links connect different autonomous systems.
I will present insights on the impact of greediness in the Network
Creation Games introduced by Fabrikant et al. [PODC'03]. Based on the
ideas that ISPs prefer smooth adaptations over radically re-designing
their infrastructure and that computing a best possible strategy is
NP-hard, I will introduce and analyze a very natural solution concept,
called the Greedy Equilibrium.
It turns out that naive greedy play leads to remarkably stable networks
in the SUM-version, where agents attempt to minimize their average
distance to all other agents. For the MAX-version, where agents attempt
to minimize their maximum distance, I will present positive results for
tree-networks and a strong negative result for general networks.