City: Saint Petersburg Novosibirsk Kazan Language: Русский English

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

What: Lecture
When: Sunday, 23 November 2014, 11:15–12:50
Where: ПОМИ РАН
Slides: streaming_algorithms_lecture_231114.pdf

Description

Спарсификаторы. Построение в полупотоковом режиме за \(\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

Video