Задача поиска совершенного паросочетания в регулярном двудольном графе — классическая задача с приложеними к реберной раскраске, маршрутизации и задачам планирования, также связанная с задачей построения разложения Биркгофа-фон Неймана бистохастических матриц. В результате ряда улучшений в 2001 г. для этой задачи был получен алгоритм с линейным временем работы.

В первой части доклада будет рассмотрена задача поиска совершенного паросочетания в регулярных двудольных графах за сублинейное время. Мы покажем, что использование вероятностных методов позволяет получить неожиданно эффективные алгоритмы для этой задачи. С другой стороны, мы покажем, что любому детерминированному алгоритму требуется как минимум линейное время.

В второй части доклада будет рассмотрена следующая коммуникационная задача: Алиса знает граф $ G_A=(P, Q, E_A) $ , Боб знает граф $ G_B=(P, Q, E_B) $, где $ |P|=|Q|=n $. Алиса может послать Бобу сообщение $ m $, зависящее только от $ G_A $, после чего Боб должен выдать паросочетание $ M\subseteq E_A\cup E_B $. Минимальный размер сообщения, которое позволяет Бобу достичь $ 1-\e $ приближения максимального паросочетания в $ G_A\cup G_B $ — это коммуникационная сложность приближения паросочетания с одним раундом, которая также дает нижнюю оценку на однопроходную потоковую сложность приближения максимального паросочетания.

В данной работе исследуется качество приближения, которое можно достичь при помощи сообщения (или памяти) размера $ \tilde O(n) $. Ранее для обеих задач было известно только приближение с коеффициентом $ 1/2 $.

Мы опишем коммуникационный протокол со сложностью $ \tilde O(n) $, при помощи которого достигается приближение с коэффициентом $ 2/3 $, а также покажем, что существенно лучшее приближение имеет сложность $ n^{1+\Omega(1/\log\log n)} $.

Данный коммуникационный протокол также позволяет получить детерминированный однопроходный потоковый алгоритм с памятью $ O(n) $, дающий приближение $ 1-1/e $ для случая, когда вершины на одной стороне графа появляются в потоке вместе со всеми инцидентными ребрами.

Совместная работа с Ашишем Гоэлем и Сандживом Канна.