Laboratory of Mathematical Logic at PDMI

Пятница, 9 апреля, ауд. 106. Начало в 19:00.

Докладчик: Александр Тискин (University of Warwick).

Тема: Приближенное решение метрической задачи о коммивояжере.

Abstract

Метрическая задача о коммивояжере - одна из классических NP-трудных задач комбинаторной оптимизации. Существуют простые и эффективные приближенные методы ее решения: метод Кристофидеса и метод "двойного дерева", каждый из которых выдает множество решений, не превосходящих оптимальное в 1.5 и в 2 раза соответственно. Мы рассматриваем задачу относительной оптимизации, то есть поиска наилучшего из решений среди множества, полученного методами Кристофидеса или "двойного дерева". В случае метода Кристофидеса, данная задача является NP-трудной даже на Евклидовой плоскости. Для метода "двойного дерева", задача тоже долгое время ошибочно считалась NP-трудной, однако недавно было получено несколько эффективных алгоритмов ее решения. Будет описан один из таких алгоритмов, а также приведены некоторые нижние оценки, экспериментальные результаты и открытые проблемы.