|[home] - [up]|
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
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.