Город: Санкт-Петербург Казань Язык: Русский English

Graph Algorithms and Continuous Optimization
Санкт-Петербург / весна 2017, посмотреть все семестры

Запишитесь на курс, чтобы получать уведомления и иметь возможность сдавать домашние задания. Для записи требуется регистрация на сайте.
Перейти к регистрации Войти

Traditionally, we view graphs as purely combinatorial objects and tend to design our graph algorithms to be combinatorial as well. In fact, in the context of algorithms, combinatorial became a synonym of fast.

Recent work, however, shows that a number of such inherently combinatorial graph problems can be solved much faster using methods that are very non-combinatorial. Specifically, by approaching these problems with tools and notions borrowed from linear algebra and, more broadly, from continuous optimization. A notable examples here are the recent lines of work on the maximum flow problem, the bipartite matching problem, and the shortest path problem in graphs with negative-length arcs.

This series of lectures will explore basic concepts that underlie these developments. The topics covered will span key continuous optimization primitives such as gradient descent method, linear system solving, and Newton's method. We will also demonstrate how these tools can be applied to graph algorithms, using the maximum flow problem as illustration.

Курс был прочитан в рамках International Computer Science Student School Recent Advances in Algorithms May 22–26, 2017

Дата и время Название Место Материалы
22 мая
Part 1: Overview, лекция ПОМИ РАН слайдывидео
22 мая
Part 2: Unconstrained Minimization, лекция ПОМИ РАН слайдывидео, файлы
23 мая
Part 3: Fast (Laplacian) Linear System Solving, лекция ПОМИ РАН слайдывидео, файлы
24 мая
Part 4, лекция ПОМИ РАН видеофайлы