Алгоритмы на графах

Общая информация
ЛекторА. Гольдберг
Семестрвесна 2010
Дата начала31.01.2010
Количество пар3
Язык курсарусский
Аннотация В миникурсе будут рассказаны последние результаты для таких задач на графах, как нахождение максимального потока и пар кратчайших расстояний.
Слайды первой лекции
Лекции Подсказка: слайды, видеозапись и другие материалы лекции доступны со страницы лекции, попасть на которую можно, нажав на её название.

1. An Efficient Point-to–Point Shortest Path Algorithm
(01.06.2008 - 13:00 - 15:00)

We study the point-to–point shortest path problem in a setting where preprocessing is allowed. The two main techniques we address are ALT and REACH. ALT is A* search with lower bounds based on landmark distances and triangle inequality. The REACH approach precomputes locality values on vertices and uses them to prune the search. We improve on REACH in several ways. In particular, we add shortcut arcs which reduce vertex reaches. Our modifications greatly reduce both preprocessing and query times. Our algorithm combines in a natural with ALT, yielding significantly better query times and allowing a wide range of time–space trade–offs. The resulting algorithms are quite practical for our motivating application, computing driving directions, both for server and for portable device applications. The ideas behind our algorithms are elegant and may have other applications as well. http://video.yandex.ru/users/pdmicsclub/view/55/
2. The Binary Blocking Flow Algorithm for the Maximum Flow Problem
(03.06.2008 - 13:00 - 15:00)

The maximum flow problem is a classical combinatorial optimization problem with numerous applications. Efficient algorithms for this problem have been studied for over half a century. For a long time, the $ O(nm) $ has been the goal of the algorithm designers, where $ n $ and $ m $ are the number of input vertices and arcs, respectively. This is a natural target as the maximum flow decomposition can have $ \Omega(nm) $ arcs. Algorithms achieving the bound for most graph densities, and coming within a factor of $ \log n $ or less for the remaining ones, have been developed. However, for the unit capacity case, the problem can be solved in $ O(\min(n^{2/3}, m^{1/2})\cdot m) $ time. The binary blocking flow algorithm extends this result to the case of integral capacities in the range $ [1\dots U] $ and achieves the bound of $ O(\min(n^{2/3}, m^{1/2})\cdot m\cdot\log(n^2/m)\cdot\log U) $. This bound is better that $ O(nm) $ unless $ U $ is huge. Whereas the previous algorithms treated all residual arcs equally, assigning them length one, our algorithm distinguishes between small and large arcs, assigning length one to the former and length zero to the latter. In this talk we describe the binary blocking flow algorithm and its analysis. We also discuss related open problems: extending the result to minimum-cost flows and obtaining practical improvements based on the ideas of the algorithm. http://video.yandex.ru/users/pdmicsclub/view/54/
3. Highway Dimension and Provably Efficient Shortest Path Algorithms
(31.01.2010 - 13:00 - 15:00)

Computing driving directions has motivated many shortest path heuristics that answer queries on continental scale networks, with tens of millions of intersections, in real time, and with very low storage overhead. We give the first theoretical analysis of several underlying algorithms on a non-trivial class of networks. To do this, we introduce the notion of highway dimension. Our analysis works for networks with low highway dimension and gives a unified explanation of good performance for several seemingly different algorithms. http://video.yandex.ru/users/pdmicsclub/view/56/
Ваша оценка: Пусто Средняя: 5 (2 голосов)
Share |
Андрей Гольдберг  и студенты клуба
 Лекция Андрея Гольдберга
Андрей Гольдберг
Андрей Гольдберг
Андрей Гольдберг