Monday, April 15, 2013
Humboldt-Universität zu Berlin
Institut für Informatik
Rudower Chaussee 25
Lecture - 14:15
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
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.