| Speaker : | Timothy G. Griffin |
| University of Cambridge | |
| Date: | 04/04/2012 |
| Time: | 2:00 pm - 3:00 pm |
| Location: | LINCS Seminars room |
Abstract
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.
This 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).
You can find the paper here: http://www.cl.cam.ac.uk/~tgg22/publications/routing_in_equilibrium_mtns_2010.pdf
Biography: Timothy G. Griffin is currently on sabbatical in Paris at PPS/INRIA-pi-r2, http://www.pps.jussieu.fr
This 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)