This is a mini-course on resent results in the area. First lectures will require minimal prerequisites: basicknowledge of graph algorithms and elementary data structures. For subsequent lectures, more prior exposure to algorithms, including approximation algorithms, will be helpful but not required.

DESCRIPTION

The point-to-point shortest path problem is a classical optimization problem. Motivated by the proliferation of GPS-based navigation systems, a lot of progress has been recently made in the area. Algorithms with preprocessing received a special attention. These algorithm precompute auxiliary data that allows answering queries in real time on a server, or in a fraction of a second on a mobile device.

Labeling algorithm precompute a label for every vertex in a graph. An s-t query is answered based on the labels of s and t, without looking at the input graph. For some classes of graphs, labels are small and queries are efficient. Hub labeling algorithms are a special kind of labeling algorithms that work well on some problem classes, in particular road networks.

After introducing hub labeling algorithms, we will discuss efficient query implementation and see why distance queries on road networks can be answered in less than a microsecond. Then we will study hub labeling preprocessing. We will start with a heuristic algorithm that works well on road networks. Next we will study the Cohen at. al. approximation algorithm for the preprocessing problem, its improvements and efficient implementations.

Cohen et. al. algorithm works well on a wider set problem classes, but cannot solve large problems in reasonable time. We will discuss the use of sampling to make the algorithm more efficient in practice. In conclusion, we will survey other results, including theoretical results on computational complexity of problems related to hub labeling.

POSSIBLE PROJECTS

A public-domain implementation of basic Hub Labeling algorithms https://github.com/savrus/hl, developed by Ruslan Savchenko, can be used as a starting point for experimental projects in the area. One can implement more sophisticated algorithms from the literature, or try their own ideas on the topic.