Приближенное решение задач комбинаторной оптимизации: алгоритмы и трудность
Курс
Приближенное решение оптимизационных задач всегда было важной частью теории оптимизации. Решение, отличающееся от оптимального на 1%, обычно удовлетворительно с практической точки зрения. За последние десятилетия приближенное решение дискретных оптимизационных задач стало к тому же одной из важнейших частей теории вычислительной сложности. Для некоторых задач были найдены (в предположении P не равно NP) границы точности приближения. Это означает, например, что существует эффективный алгоритм поиска решения, отличающегося не более чем вдвое от оптимального, но нет такого алгоритма для поиска решения, которое отличалось бы не более чем в 1.9999 раза, количество девяток произвольное. Для других задач точные границы приближения получены лишь в предположении более сильной гипотезы (знаменитая Unique Games Conjecture). Справедливость UGC — один из самых горячих
вопросов современной теории сложности.
В курсе будут приведены основные примеры приближенных алгоритмов, основанных на решении задач выпуклой оптимизации. Вторая часть курса: обсуждение способов доказательств трудности приближенного решения. Одной из привлекательных особенностей данной области является разнообразие используемой в ней математики: алгоритмы, графы, вероятность, геометрия, анализ Фурье. По той же причине рассуждения в этой области технически трудны. В курсе будет сделана попытка прояснить основную канву рассуждений, оставляя в стороне доказательства самых трудных теорем.