Город: Тест Санкт-Петербург Новосибирск Казань Язык: Русский English

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

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

Описание

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