• 15 июня, четверг
  • Москва, Кочновский проезд, 3

Mini-course "The Matching Problem: Approaches, Applications, and Algorithms" - Stephen Fenner (University of South Carolina)

Регистрация на событие закрыта

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

Другие события организатора

Школа Прикладной Математики и Информатики МФТИ
185 дней назад
15 июня, начало в 18:10
Москва
Кочновский проезд, 3

Подробности и регистрация: cs.hse.ru/en/big-data/tcs-lab/fenne...

On June 15-16, 2017 Stephen Fenner (University of South Carolina) will give a mini-course "The matching problem: Approaches, applications, and algorithms".

Address: Faculty of computer science, Kochnovsky proezd, 3.
Language: English

Schedule:
15.06.2017     18:10-19:30 (room 317)
16.06.2017     16:40-19:30 (room 317)

Participation is free, but the registration is needed.
If you have questions, please contact the manager of the laboratory Ekaterina Vavilova: evavilova@hse.ru.

Abstract 

The matching problem in graphs is central to graph theory and combinatorics, with a host of related problems and connections. In this minicourse, we will discuss historical approaches to this problem, including Koenig’s Minimax theorem (which ties together several results, including the Marriage theorem and Hall’s theorem), as well as the problem’s connection to matrix determinants, network flows and cuts, matroids (time permitting) and geometry (such as the matching polytope). We will review fast sequential algorithms for matching, including the reduction to max flow for bipartite graphs and Edmonds’s algorithm for matching in general graphs. Finally, we look at newer ways to parallelize matching algorithms, including the Isolation lemma and its use in finding fast, randomized parallel algorithms for matching, and new geometry-based ways to partially derandomize these algorithms.

Регистрация

Рекомендуемые события

Организуете события? Обратите внимание на TimePad!

Профессиональная билетная система, статистика продаж 24/7, выгрузка списков участников, встроенные инструменты продвижения, личный кабинет для самостоятельного управления и еще много чего интересного.

Узнать больше