[home] - [up]


Lectures and Colloquia during the semester



Monday, February 7, 2005

Technische Universität Berlin
Straße des 17. Juni 136
10623 Berlin
Math building - Room MA 041           - map -
Lecture - 14:15

Stefano Leonardi -University of Rome "La Sapienza"

Cost-sharing mechanisms for Network Design

Abstract: Today's Internet seamlessly connects billions of users that mostly pursue selfish motives in both, single-handed and collaborative ways. By design the Internet is anarchic and hence, it is devoid of a central authority that possesses global knowledge and the power to regulate the agents' behavior. In this talk we focus on the design of so called 'mechanisms' that encourage truthful and fair behavior among the agents/users by means of issuing rewards and by postulating interaction rules.

We present a first mechanism able to share between users in a fair manner the cost of a Steiner forest that connects a set of terminal pairs. This mechanism is also proved to recover at least 1/2 the cost of the solution. This mechanism is a primal dual algorithm based on a new linear programming relaxation that is shown strictly stronger that the classical undirected cut relaxation. We also prove that no such mechanism can recover more than 1/2 of the cost of the solution for the Steiner tree game, therefore implying tightness of our result.

This is joint work with Guido Schaefer at Universita' di Roma "La Sapienza", Italy, Jochen Koenemann at University of Waterloo, Canada, and Stefan van Zwam at Eindhoven University of Technology, The Netherlands.


Colloquium - 16:00

Heiko Schilling -Technische Universität Berlin

Flows over Time: Towards a more Realistic and Computationally Tractable Model

Abstract: We introduce a novel model for "flows over time" which captures the behaviour of cars traveling through a road network better than previous models. We show that computing an optimal solution in the new model is NP-hard and present an LP-based algorithm which we evaluate with several experiments on real world data of road networks and generated requests. Among other things we compare the quality of the solutions with solutions generated by an FPTAS for a related but considerably less realistic model.


[home] - [up] - [top]