City: Saint Petersburg Novosibirsk Kazan Language: Русский English

Приближённые алгоритмы для задачи коммивояжёра
Algorithms for NP-hard problems

What: Lecture
When: Sunday, 06 October 2013, 11:15–12:50
Where: ПОМИ РАН

Description

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

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

Video