Пятница 06.10. Юрий Макарычев (Toyota Technological Institute at Chicago): "Алгоритмы для решения устойчивых задач комбинаторной оптимизации"

Speaker: 
Юрий Макарычев (Toyota Technological Institute at Chicago)
Date: 
Friday, October 6, 2017 - 18:00
Place: 
ПОМИ РАН, ауд. 106
Abstract: 

Мы обсудим понятие устойчивости для задач комбинаторной оптимизации и кластеризации, предложенное Билу и Линиалом (2010). Задача называется α-устойчивой, если её оптимальное решение не меняется, когда мы немного изменяем её параметры (а именно умножаем каждый параметр на число между 1 и α). Мы расскажем об алгоритмах для решения стабильных задач комбинаторной оптимизации и кластеризации, таких как k-means, k-median, Max Cut, and Minimum Multiway Cut. Мы также представим несколько результатов о сложности решения стабильных задач.

Доклад основан на совместных работах с Харисом Анджелидакисом, Аравинданом Виджейарагаваном и Константином Макарычевым.