School of Mathematical Sciences Colloquium Series |
Routing in Equilibrium
by
Dr Timothy G. Griffin
Location: Napier LG 24
Date: Tuesday, 21 June
Time: 15:10
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 algebras
using algorithms in the Bellman-Ford family.
However, no polynomial time bound was known
for such algorithms. In this talk, we show that
routing equilibria can be computed using
Dijkstra's algorithm for one class of non-distributive
structures. 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 presented at the 19th International
Symposium on Mathematical Theory of Networks and Systems (MTNS 2010).
You can find the paper here.
The Colloquium will be followed by a reception for our speaker in
the Staff Tea Room with wine and nibbles to which all are invited.