Seminario Interdipartimentale di Algoritmica  

Monday, March 6, 2006, 12:00 noon
On the Price of Stability for Designing Undirected Networks with Fair Cost Allocations
Amos Fiat, School of Computer Science, Tel Aviv University

DI - Department of Computer Science
Seminar Room, third floor

Abstract:

In this work we address the open problem of bounding the price of stability for a network design game with fair cost allocations in undirected graphs posed in "The Price of Stability for Network Design with Fair Cost Allocation" (Anshelevich et. al). For the version of this problem that we consider, every vertex is associated with a selfish player, and there is a distinguished source node to which all players must connect. We show that the price of stability is O(loglog n).

Amos Fiat, Haim Kaplan, Meital Levy, Svetlana Olonetsky, and Ronen Shabo