Shortest path problems are among the most fundamental optimization problems with many applications. The project is devoted to theoretical and experimental study of algorithms for the shortest path and related problems, including single-source, feasibility, minimum mean cycle, and point-to-point shortest paths.
The problem of finding shortest paths in graphs is a fundamental optimization problem with many applications. The problem has several variants. Algorithms with near-optimal efficiency, either in theory or in practice, are known for some problem variants, such as the single-source problem. For other variants, significant improvement over the current state of the art may be possible.
A significant effort of the SPA project is devoted to the following variant of the shortest path problem. Given a graph, we preprocess it subject to the restriction that the space for the preprocessing results is limited (e.g., a small constant times the space used to store the graph). Then we would like to quickly answer queries on single-pair shortest paths. This is a natural variant of the problem as in many applications, such as that of computing driving directions (e.g., Google Maps, Yahoo! Maps, Bing Maps).
We developed several techniques for speeding up classical algorithms for the problem. These include landmark-based A* search, reach-based pruning, and their combinations. The resulting algorithms are very practical and can be used on servers, desktops, or portable devices (e.g., car navigation systems). Some of these algorithms are being used by Bing Maps. With Hub Labels, we have the fastest known point-to-point shortest path queries on road networks.
More recently, within our Customizable Route Planning project, we have been looking at even more flexible approaches, which allow for real-time traffic updates, blocked roads, personalized (customized) driving directions, reasonable alternative paths, and many other features. To achieve this, we use our own state-of-the-art graph partitioning algorithm, PUNCH.
Other problems we have studied include shortest path feasibility, minimum cycle mean problems, and hardware-accelerated shortest path trees (PHAST), using both multicore and GPUs. Our research lead to better understanding the practical performance of existing algorithms and the development of new algorithms with good practical performance.
Additional details about our results can be found in project publications.
- Boris V. Cherkassky
- Amos Fiat
- Chris Harrelson
- Haim Kaplan
- Thomas Pajor
- Ilya Razenshteyn
- Daniel Delling, Andrew V. Goldberg, and Renato F. Werneck, Hub Label Compression, in Proc. 12th International Symposium on Experimental Algorithms, Springer Verlag, 2013
- Maxim Babenko, Andrew V. Goldberg, Anupam Gupta, and Viswanath Nagarajan, Algorithms for Hub Label Optimization, in 40th International Colloquium on Automata, Languages and Programming (ICALP 2013), Springer Verlag, 2013
- Andrew V. Goldberg, Ilya Razenshteyn, and Ruslan Savchenko, Separating Hierarchical and General Labelings, in Proc. 38th Int. Symp. on Math. Found. of CS (MFCS 2013), Springer Verlag, 2013
- Ittai Abraham, Daniel Delling, Amos Fiat, Andrew V. Goldberg, and Renato F. Werneck, HLDB: Location-Based Services in Databases, in SIGSPATIAL GIS, ACM, November 2012
- Ittai Abraham, Daniel Delling, Amos Fiat, Andrew V. Goldberg, and Renato F. Werneck, HLDB: Location-Based Services in Databases, no. MSR-TR-2012-59, June 2012
- Ittai Abraham, Daniel Delling, Andrew V. Goldberg, and Renato F. Werneck, Hierarchical Hub Labelings for Shortest Paths, no. MSR-TR-2012-46, April 2012
- Daniel Delling, Andrew V. Goldberg, Andreas Nowatzyk, and Renato F. Werneck, PHAST: Hardware-accelerated shortest path trees, in Journal of Parallel and Distributed Computing, Elsevier, 2012
- Ittai Abraham, Daniel Delling, Andrew V. Goldberg, and Renato F. Werneck, Hierarchical Hub Labelings for Shortest Paths, in Proceedings of the 20th Annual European Symposium on Algorithms (ESA'12), Springer, 2012
- Andrew V. Goldberg, Highway Dimension: From Practice to Theory and Back, in INFORMS OS Today, vol. 2, no. 1, pp. 12--16, INFORMS, 2012
- Ittai Abraham, Daniel Delling, Andrew V. Goldberg, and Renato F. Werneck, A Hub-Based Labeling Algorithm for Shortest Paths on Road Networks, in Proceedings of the 10th International Symposium on Experimental Algorithms (SEA'11), Springer Verlag, May 2011