Monday, November 30, 2009
Technische Universität Berlin
Fakultät II, Institut für Mathematik
Str. des 17. Juni 136,
room MA 041
Lecture - 14:15
Abstract:
In the past decades the G(n,p) model of random graphs, introduced by Erdös and Renyi in the 60's, has led to numerous beautiful and deep results. A key feature that is used in basically all proofs is that edges in G(n,p) appear independently. This situation changes dramatically if one considers graph classes with structural side constraints.
For example, in a random planar graph Pn (a graph drawn uniformly at random from the class of all labeled planar graphs on n vertices) the edges are obviously far from being independent. In this talk we show that recent progress in the construction of Boltzmann samplers can be used to reduce the study of properties of combinatorial objects to properties of sequences of independent and identically distributed random variables -- to which we can then again apply well known machinery from random graph theory.
Colloquium - 16:00
Abstract:
Joint work with Vincenzo Bonifaci and Guido Schaefer.
We study the impact of Stackelberg routing to reduce the price of anarchy in
network routing games. In this setting, a constant fraction of the entire
demand is routed centrally according to a predefined Stackelberg strategy and
the remaining demand is routed selfishly by nonatomic players. We exhibit a
family of single-commodity networks for which every Stackelberg strategy has
price of anarchy at least proportional to the size of the network, and we
exhibit a Stackelberg strategy with price of anarchy bounded by a function of
the size of the network. We also give improved bounds on the price of anarchy
induced by specific Stackelberg strategies in other cases, such as when the
latency functions are polynomials of bounded degree.