Monday, April 30, 2012
Technische Universität Berlin
Institut für Mathematik
Str. des 17. Juni 136
10623 Berlin
room MA 041
Lecture - 14:15
Abstract:
In machine scheduling problems a number of jobs have to be
processed by a set of machines so as to minimize a certain objective
function (e.g., the makespan or the total completion time). In this
talk we consider a game-theoretic framework in which the jobs are the
players who selfishly choose a machine so as to minimize their own
completion time. We will consider different machine environments and
in each we will give bounds on the price of anarchy (poa) of the
underlying game with respect to the total completion time. In
particular, the different environments will allow us to explore three
different general techniques for bounding the poa in these or related
games.
The talk includes joint work with R. Cole, V. Gkatzelis, V. Mirrokni,
N. Olver, M. Queyranne, O. Rivera, and T. Vredeveld.
Colloquium - 16:00
Abstract:
A classic experiment by Milgram shows that individuals can route messages along short paths in social networks, given only simple categorical information about recipients (such as "he is a prominent lawyer in Boston" or "she is a Freshman sociology major at Harvard"). That is, these networks have very short paths between pairs of nodes (the so-called small-world phenomenon); moreover, participants are able to route messages along these paths even though each person is only aware of a small part of the network topology.
Some sociologists conjecture that participants in such scenarios use a greedy routing strategy in which they forward messages to acquaintances that have more categories in common with the recipient than they do, and similar strategies have recently been proposed for routing messages in dynamic ad-hoc networks of mobile devices.
In this talk, we introduce a network property called membership dimension, which characterizes the cognitive load required to maintain relationships between participants and categories in a social network. We show that any connected network has a system of categories that will support greedy routing, but that these categories can be made to have small membership dimension if and only if the underlying network exhibits the small-world phenomenon.
Joint work with Darren Strash, David Eppstein, Lowell Trott, and Michael T. Goodrich