Andrew Goldberg: Shortest Path Algorithms: Theory and Practice скачать в хорошем качестве

Andrew Goldberg: Shortest Path Algorithms: Theory and Practice

Videos from Beyond Worst Case Analysis Workshop Stanford, CA; Sept 19-21, 2011 http://theory.stanford.edu/~tim/bwca/... Andrew Goldberg: Shortest Path Algorithms: Theory and Practice In this talk we examine the interaction between theoretical analysis and practical evaluation of algorithms. Empirical observations lead to theoretical models, algorithm design and theoretical analysis. Experimental evaluation of the resulting algorithm can either validate the theory or refine it. Refinements can lead to algorithms with better correspondence between theoretical bounds and practical performance. This theory -- experimentation cycle is an example of the scientific method. We illustrate this process using point-to-point shortest path algorithms for road networks as an example. We describe how some of the recent algorithms with good experimental and practical performance leads to the theoretical notion of highway dimension, which allows theoretical analysis of the underlying methods. The analysis gives insight into the algorithm performance and introduces an unexpected relationship between shortest paths and VC-dimension. The analysis also suggests that the hub labeling algorithm, never previously studied in the context of large road networks, has better runtime bound than those for the best previous implementations. This motivates an implementation and an empirical study of the hub labeling algorithm, which turns out to be faster in practice as well. We also apply the some of the above-mentioned techniques to the one-to-all shortest path problem. In theory, this problem can be solved by Dijkstra's algorithm in (essentially) linear time. However, this time bound is for a word RAM model of computation that ignores modern computer architecture features such as locality and parallelism. We describe a new algorithm for the problem that takes advantage of these features to obtain a speedup of up to three orders of magnitude over Dijkstra's algorithm on continental-size networks. This work shows the limitations of theoretical analysis for predicting real-life algorithm performance and the power of the scientific method applied to algorithm design. Joint work with Ittai Abraham, Daniel Delling, Amos Fiat, Andreas Nowatzyk, and Renato Werneck.