2009 | OriginalPaper | Chapter
Speed-Up Techniques for the Selfish Step Algorithm in Network Congestion Games
Authors : Matthias Kirschner, Philipp Schengbier, Tobias Tscheuschner
Published in: Experimental Algorithms
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
Recently, many speed-up techniques were developed for the computation of shortest paths in networks with rather static edge latencies. Very little is known about dealing with problems which rely on the computation of shortest paths in highly dynamic networks. However, with an increasing amount of traffic, static models of networks rather sparsely reflect realistic scenarios. In the framework of network congestion games, the edge latencies depend on the number of users traveling on the edges. We develop speed-up techniques for the selfish step algorithm to efficiently compute (pure) Nash equilibria in network congestion games. Our approaches
1
periodically compute estimations for lengths of shortest paths during the advance of the selfish step algorithm with the purpose to use
A
*
for many path computations, and
1
completely save many path computations or substitute them by more efficient tests.
In comparison to an implementation of the selfish-step algorithm using Dijkstra’s algorithm we improve the total running time by a factor of 4 up to 9 on highway networks and grids.