Laboratory of Mathematical Logic at PDMI

Пятница, 6 октября, ПОМИ РАН, ауд. 106. Начало в 18:00.

Докладчик: Юрий Макарычев (Toyota Technological Institute at Chicago).

Тема: Алгоритмы для решения устойчивых задач комбинаторной оптимизации.

Abstract

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

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