BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//talks.cam.ac.uk//v3//EN
BEGIN:VTIMEZONE
TZID:Europe/London
BEGIN:DAYLIGHT
TZOFFSETFROM:+0000
TZOFFSETTO:+0100
TZNAME:BST
DTSTART:19700329T010000
RRULE:FREQ=YEARLY;BYMONTH=3;BYDAY=-1SU
END:DAYLIGHT
BEGIN:STANDARD
TZOFFSETFROM:+0100
TZOFFSETTO:+0000
TZNAME:GMT
DTSTART:19701025T020000
RRULE:FREQ=YEARLY;BYMONTH=10;BYDAY=-1SU
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
CATEGORIES:Semantics Lunch (Computer Laboratory)
SUMMARY:Convergence of path-finding - Alex Gurney
DTSTART;TZID=Europe/London:20081124T124500
DTEND;TZID=Europe/London:20081124T140000
UID:TALK14774AThttp://talks.cam.ac.uk
URL:http://talks.cam.ac.uk/talk/index/14774
DESCRIPTION:It is well-known that finding shortest paths in a
graph corresponds to\nsolving a matrix equation\,
and that this can be done by an iterative\nprocess
. This is guaranteed to converge to a fixed point
if the\nunderlying algebra of the matrix elements
has certain properties.\n\nWe will look at the rel
ated notion of a "stable paths problem"\, where\nt
he solution that is sought is not an optimal short
est-paths tree\,\nbut a Nash equilibrium of path a
ssignments. The same matrix methods\ncan be used t
o solve this problem\, but the algebraic propertie
s involved\nare different.\n\nThis talk will conce
ntrate on proofs of convergence for the matrix\nit
eration\, and the associated problem of how many i
teration steps may\nbe required before a fixed poi
nt is reached.
LOCATION:FW26
CONTACT:Matthew Parkinson
END:VEVENT
END:VCALENDAR