University of Cambridge > Talks.cam > Semantics Lunch (Computer Laboratory) > Convergence of path-finding

Convergence of path-finding

Add to your list(s) Download to your calendar using vCal

  • UserAlex Gurney
  • ClockMonday 24 November 2008, 12:45-14:00
  • HouseFW26.

If you have a question about this talk, please contact Matthew Parkinson.

It is well-known that finding shortest paths in a graph corresponds to solving a matrix equation, and that this can be done by an iterative process. This is guaranteed to converge to a fixed point if the underlying algebra of the matrix elements has certain properties.

We will look at the related notion of a “stable paths problem”, where the solution that is sought is not an optimal shortest-paths tree, but a Nash equilibrium of path assignments. The same matrix methods can be used to solve this problem, but the algebraic properties involved are different.

This talk will concentrate on proofs of convergence for the matrix iteration, and the associated problem of how many iteration steps may be required before a fixed point is reached.

This talk is part of the Semantics Lunch (Computer Laboratory) series.

Tell a friend about this talk:

This talk is included in these lists:

Note that ex-directory lists are not shown.

 

© 2006-2020 Talks.cam, University of Cambridge. Contact Us | Help and Documentation | Privacy and Publicity