Лекция 4. Решение оптимизационных задач: вероятностное округление
Обзорный курс по теоретической информатике


Что: Лекция
Когда: Четверг, 29 сентября 2016, 18:30–19:50
Где: ПОМИ РАН

Описание

Приближенные алгоритмы для MaxSAT: 1/2-приближенный, задача линейного программирования, (1-1/e)-приближенный алгоритм с помощью вероятностного округления. Комбинированный 3/4-приближенный алгоритм.