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

Приближённые алгоритмы для задачи коммивояжёра
Алгоритмы для NP-трудных задач


Что: Лекция
Когда: Воскресенье, 06 октября 2013, 11:15–12:50
Где: ПОМИ РАН

Описание

Лемма Шварца-Зиппеля. [wikipedia]

Приближённые алгоритмы: 1.5-приближённый алгоритм для задачи коммивояжёра в метрическом пространстве, неприближаемость общего случая, 0.5-приближение для максимизационного варианта. [CLR01, V01]

Видео