Полупотоковые алгоритмы на графах. Эскизы, разрезы, спарсификаторы
Алгоритмы обработки потоковых данных


Что: Лекция
Когда: Воскресенье, 23 ноября 2014, 11:15–12:50
Где: ПОМИ РАН
Слайды: streaming_algorithms_lecture_231114.pdf

Описание

Спарсификаторы. Построение в полупотоковом режиме за \(\tilde{O}(\varepsilon^{-2} n)\). Набросок построения в режиме offline. Эскиз графа через матрицу инциндентности. \(l_0\)-сэмплирование. Поиск компонент связности через эскизы, k-связность и поиск минимального разреза.


Спарсификаторы offline за \(\tilde{O}(\varepsilon^{-2}n)\), Nicholas Harvey + ссылка на курс CPSC 536N

Data Streams & Communication Complexity, McGregor, Amherst (про эскизы графов, разрезы и k-связность)

On Unifying the Space of \(l_0\)-Sampling Algorithms, Cormode, Firmani

Видео

Материалы