BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//talks.cam.ac.uk//v3//EN
BEGIN:VTIMEZONE
TZID:Europe/London
BEGIN:DAYLIGHT
TZOFFSETFROM:+0000
TZOFFSETTO:+0100
TZNAME:BST
DTSTART:19700329T010000
RRULE:FREQ=YEARLY;BYMONTH=3;BYDAY=-1SU
END:DAYLIGHT
BEGIN:STANDARD
TZOFFSETFROM:+0100
TZOFFSETTO:+0000
TZNAME:GMT
DTSTART:19701025T020000
RRULE:FREQ=YEARLY;BYMONTH=10;BYDAY=-1SU
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
CATEGORIES:Computer Laboratory Systems Research Group Seminar
SUMMARY:Routing in Equilibrium - Timothy G. Griffin (Unive
rsity of Cambridge)
DTSTART;TZID=Europe/London:20101014T160000
DTEND;TZID=Europe/London:20101014T170000
UID:TALK26539AThttp://talks.cam.ac.uk
URL:http://talks.cam.ac.uk/talk/index/26539
DESCRIPTION:Some path problems cannot be modelled using semiri
ngs because the associated algebraic structure is
not distributive. Rather than attempting to comput
e globally optimal paths with such structures\, it
may be sufficient in some cases to find locally o
ptimal paths --- paths that represent a stable loc
al equilibrium. For example\, this is the type of
routing system that has evolved to connect Intern
et Service Providers (ISPs) where link weights imp
lement bilateral commercial relationships between
them. Previous work has shown that routing equilib
ria can be computed for some non-distributive alge
bras using algorithms in the Bellman-Ford family.\
nHowever\, no polynomial time bound was known for
such algorithms.\nIn this talk\, we show that rout
ing equilibria can be computed using Dijkstra's al
gorithm for one class of non-distributive structur
es. This provides the first polynomial time algori
thm for computing locally optimal solutions to pat
h problems.\n\nThis is joint work with João Luís S
obrinho (http://www.lx.it.pt/~jls/) presented at t
he 19th International Symposium on Mathematical Th
eory of Networks and Systems (MTNS 2010).\nYou can
find the paper here:\nhttp://www.cl.cam.ac.uk/use
rs/tgg22/publications/routing_in_equilibrium_mtns_
2010.pdf\n
LOCATION:FW26\, Computer Laboratory\, William Gates Builidi
ng
CONTACT:Eiko Yoneki
END:VEVENT
END:VCALENDAR