Algorithmic methods laboratory

Hub labeling

Speaker:

Всеволод Опарин

Date:

Wednesday, August 5, 2015 - 18:00

Abstract:

Посмотрим на задачу кратчайших путей в графе. Нам разрешается сделать
некоторый предподсчет, а потом нужно быстро отвечать на запросы, какое
расстояние между заданными вершинами. Можно посчитать матрицу
расстояний, но это потребует O(n^2) памяти. Для экономии памяти
используют метод Hub Labeling.

Для каждой вершины u выбирают некоторое множество хабов H_u, других
вершин графа, и до каждого хаба считают расстояние. Если у пары вершин
есть общий хаб на кратчайшем пути, то можно восстановить расстояние
между ними. Нужно расставить хабы так, чтобы между каждой парой вершин
можно было посчитать расстояние.

В задаче оптимизируют разные функции. Например в HL_1 минимизируют
суммарный размер хабов, в HL_inf минимизируют максимальный размер.

Результаты, которые хочу рассказать.
- log n приближение в общем случае
- log d приближение для случая уникальных путей, где d -- диаметр.
- log n неприближаемость HL_1
- log n неприближаемость HL_inf