COOKIES: By using this website you agree that we can place Google Analytics Cookies on your device for performance monitoring. |

University of Cambridge > Talks.cam > Computer Laboratory Systems Research Group Seminar > Routing in Equilibrium

## Routing in EquilibriumAdd to your list(s) Download to your calendar using vCal - Timothy G. Griffin (University of Cambridge)
- Thursday 14 October 2010, 16:00-17:00
- FW26, Computer Laboratory, William Gates Builiding.
If you have a question about this talk, please contact Eiko Yoneki. 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 (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/users/tgg22/publications/routing_in_equilibrium_mtns_2010.pdf This talk is part of the Computer Laboratory Systems Research Group Seminar series. ## This talk is included in these lists:- All Talks (aka the CURE list)
- CL's SRG seminar
- Cambridge Centre for Data-Driven Discovery (C2D3)
- Chris Davis' list
- Computer Laboratory Systems Research Group Seminar
- Computer Laboratory talks
- FW26, Computer Laboratory, William Gates Builiding
- Interested Talks
- School of Technology
- Trust & Technology Initiative - interesting events
- bld31
- ndk22's list
- rp587
Note that ex-directory lists are not shown. |
## Other listsEarthing Spirituality NanoScience Seminar AMOP/TCM Seminar## Other talkstba Production Processes Group Seminar - "Advanced water filtration platforms based on hierarchically structured carbon nanotubes." Queer stories at the Museum Options and Opportunities for Health Data Science Atmospheric Retrieval |