BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//wp-events-plugin.com//7.2.3.1//EN
BEGIN:VEVENT
UID:164@lincs.fr
DTSTART;TZID=Europe/Paris:20120404T140000
DTEND;TZID=Europe/Paris:20120404T150000
DTSTAMP:20170328T124455Z
URL:https://www.lincs.fr/events/routing-in-equilibrium/
SUMMARY:Routing in equilibrium
DESCRIPTION:Some path problems cannot be modelled using semirings because
 the associated algebraic structure is not distributive. Rather than
 attempting to compute globally optimal paths with such structures\, it may
 be sufficient in some cases to find locally optimal paths - paths that
 represent a stable local equilibrium.For example\, this is the type of
 routing system that has evolved to connect Internet Service Providers
 (ISPs) where link weights implement bilateral commercial relationships
 between them.Previous work has shown that routing equilibria can be
 computed for some non-distributive algebra susing algorithms in the
 Bellman-Ford family.However\, no polynomial time bound was knownfor such
 algorithms. In this talk\, we show thatrouting equilibria can be computed
 using Dijkstra's algorithm for one class of non-distributivestructures.
 This provides the first polynomial time algorithm for computing locally
 optimal solutions to path 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 Mathematical Theory of Networks and Systems
 (MTNS 2010).\n\nYou can find the paper here:
 http://www.cl.cam.ac.uk/~tgg22/publications/routing_in_equilibrium_mtns_201
 0.pdf\n\nBiography: Timothy G. Griffin is currently on sabbatical in Paris
 at PPS/INRIA-pi-r2\, http://www.pps.jussieu.fr\n\nThis file
 http://www.cl.cam.ac.uk/~tgg22/metarouting/rie-1.0.v is a first cut at
 formalizing these results using Coq (http://coq.inria.fr) with ssreflect
 (http://www.msr-inria.inria.fr/Projects/math-components)
CATEGORIES:Seminars,Youtube
LOCATION:LINCS Seminars room\, 23\, avenue d'Italie\, Paris\, 75013\,
 France
GEO:48.828400;2.356897
X-APPLE-STRUCTURED-LOCATION;VALUE=URI;X-ADDRESS=23\, avenue d'Italie\,
 Paris\, 75013\, France;X-APPLE-RADIUS=100;X-TITLE=LINCS Seminars
 room:geo:48.828400,2.356897
END:VEVENT
BEGIN:VTIMEZONE
TZID:Europe/Paris
X-LIC-LOCATION:Europe/Paris
BEGIN:DAYLIGHT
DTSTART:20120325T030000
TZOFFSETFROM:+0100
TZOFFSETTO:+0200
TZNAME:CEST
END:DAYLIGHT
END:VTIMEZONE
END:VCALENDAR