Дробно-линейные задачи об упаковке и покрытии: различия между версиями

Теоремы 1 и 2 можно применить для улучшения времени выполнения алгоритма Ленстры, Шмойса и Тардош [ ] для планирования несвязанных параллельных машин без вытеснения <math>(R||C_{max})</math>. Пусть N заданий нужно спланировать для M машин, чтобы каждое задание i было включено в план ровно для одной машины j с временем обработки <math>p_{ij}</math>, так, чтобы совокупное время обработки по всем машинам было минимальным. Тогда для любого фиксированного r > 1 существует детерминированный алгоритм (1 + r)-аппроксимации, выполняющийся за время <math>O(M^2N \; log^2 N \; log \; M)</math>, и рандомизированная версия, выполняющаяся за ожидаемое время <math>O(M N \; log \; M \; log \; N)</math>. Для версии задачи с вытеснением существуют схемы аппроксимации с полиномиальным временем выполнения, требующие <math>O(M N^2 log^2 N)</math> времени и <math>O(M N \; log \; N \; log \; M)</math> ожидаемого времени для детерминированного и рандомизированного случая, соответственно.

Для метрической задачи коммивояжера для N вершин хорошо известна граница Хельда-Карпа [2], которую можно представить как оптимум линейной программы над политопом с удалением подциклов. Используя рандомизированный алгоритм нахождения минимального разреза Каргера и Штейна [3], можно получить рандомизированную схему аппроксимации, вычисляющую границу Хельда-Карпа за ожидаемое время <math>O(N^4 log^6 N)</math>.