4551
правка
Дробно-линейные задачи об упаковке и покрытии: различия между версиями
Перейти к навигации
Перейти к поиску
м
Дробно-линейные задачи об упаковке и покрытии (посмотреть исходный код)
Версия от 22:33, 20 декабря 2018
, 20 декабря 2018→Применение
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) м (→Применение) |
||
| Строка 120: | Строка 120: | ||
Для метрической задачи коммивояжера для N вершин хорошо известна граница Хельда-Карпа [2], которую можно представить как оптимум линейной программы над ''политопом с удалением подциклов''. Используя рандомизированный алгоритм нахождения минимального разреза Каргера и Штейна [3], можно получить рандомизированную схему аппроксимации, вычисляющую границу Хельда-Карпа за ожидаемое время <math>O(N^4 \; log^6 N)</math>. | Для [[Метрическая задача коммивояжера|метрической задачи коммивояжера]] для N вершин хорошо известна граница Хельда-Карпа [2], которую можно представить как оптимум линейной программы над ''политопом с удалением подциклов''. Используя рандомизированный алгоритм нахождения минимального разреза Каргера и Штейна [3], можно получить рандомизированную схему аппроксимации, вычисляющую границу Хельда-Карпа за ожидаемое время <math>O(N^4 \; log^6 N)</math>. | ||
== Открытые вопросы == | == Открытые вопросы == | ||