BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Talks.cam//talks.cam.ac.uk//
X-WR-CALNAME:Talks.cam
BEGIN:VEVENT
SUMMARY:Routing in Equilibrium - Timothy G. Griffin (University of Cambrid
 ge)
DTSTART:20101014T150000Z
DTEND:20101014T160000Z
UID:TALK26539@talks.cam.ac.uk
CONTACT:Eiko Yoneki
DESCRIPTION:Some path problems cannot be modelled using semirings because 
 the associated algebraic structure is not distributive. Rather than attemp
 ting to compute globally optimal paths with such structures\, it may be su
 fficient in some cases to find locally optimal paths --- paths that repres
 ent a stable local equilibrium.  For example\, this is the type of routing
  system that has evolved to connect Internet Service Providers (ISPs) wher
 e link weights implement bilateral commercial relationships between them. 
 Previous work has shown that routing equilibria can be computed for some n
 on-distributive algebras using algorithms in the Bellman-Ford family.\nHow
 ever\, no polynomial time bound was known for such algorithms.\nIn this ta
 lk\, we show that routing equilibria can be computed using Dijkstra's algo
 rithm for one class of non-distributive structures. This provides the firs
 t polynomial time algorithm for computing locally optimal solutions to pat
 h problems.\n\nThis is joint work with João Luís Sobrinho (http://www.lx
 .it.pt/~jls/) presented at the 19th International Symposium on Mathematica
 l Theory of Networks and Systems (MTNS 2010).\nYou can find the paper here
 :\nhttp://www.cl.cam.ac.uk/users/tgg22/publications/routing_in_equilibrium
 _mtns_2010.pdf\n
LOCATION:FW26\, Computer Laboratory\, William Gates Builiding
END:VEVENT
END:VCALENDAR