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

  Browse A-Z

Log in

Googledetails Microsoftdetails

🔐 Log In

Information on

Subscribing to talksdetails Finding a talkdetails Adding a talkdetails Disseminating talksdetails Help and Documentationdetails

ℹī¸ Information

Convergence of path-finding

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.

This talk is included in these lists:

Note that ex-directory lists are not shown.

Other lists

Biology Hopkins Building, Seminar Room 1 Main Lecture Theatre, Divinity School, St John's College, Cambridge

Other talks

Sheref Mansy, topic TBA Title abstract tbc Peri-Operative Medicine, and Obstetrics and Gynaecology Quantum optics with organic molecules Rothschild Public Lecture: Forty years of causal inference: Report of a great-grandfather TBC
 

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