BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Talks.cam//talks.cam.ac.uk//
X-WR-CALNAME:Talks.cam
BEGIN:VEVENT
SUMMARY:Convergence of path-finding - Alex Gurney
DTSTART:20081124T124500Z
DTEND:20081124T140000Z
UID:TALK14774@talks.cam.ac.uk
CONTACT:Matthew Parkinson
DESCRIPTION:It is well-known that finding shortest paths in a graph corres
 ponds to\nsolving a matrix equation\, and that this can be done by an iter
 ative\nprocess. This is guaranteed to converge to a fixed point if the\nun
 derlying algebra of the matrix elements has certain properties.\n\nWe will
  look at the related notion of a "stable paths problem"\, where\nthe solut
 ion that is sought is not an optimal shortest-paths tree\,\nbut a Nash equ
 ilibrium of path assignments. The same matrix methods\ncan be used to solv
 e this problem\, but the algebraic properties involved\nare different.\n\n
 This talk will concentrate on proofs of convergence for the matrix\niterat
 ion\, and the associated problem of how many iteration steps may\nbe requi
 red before a fixed point is reached.
LOCATION:FW26
END:VEVENT
END:VCALENDAR