4501
правка
Евклидова задача коммивояжера: различия между версиями
Перейти к навигации
Перейти к поиску
Евклидова задача коммивояжера (посмотреть исходный код)
Версия от 14:41, 23 января 2014
, 23 января 2014→Применение
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 94: | Строка 94: | ||
Техники, разработанные Аророй [1] и Митчеллом [13], также привели к созданию квазиполиномиальных схем аппроксимации – то есть алгоритмов с временем исполнения | Техники, разработанные Аророй [1] и Митчеллом [13], также привели к созданию квазиполиномиальных схем аппроксимации – то есть алгоритмов с временем исполнения <math>n^{O(log \; n}</math>. К примеру, Арора и Карокостас [4] создали схему аппроксимации с квазиполиномиальным временем исполнения для решения евклидовой задачи нахождения минимального времени ожидания; Реми и Стегер [16] предложили схему аппроксимации с полиномиальным временем исполнения для решения задачи триангуляции с минимальным весом. | ||
Более подробные обзоры можно найти в [2] и [10]. | Более подробные обзоры можно найти в [2] и [10]. | ||