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

Представленные выше результаты могут использоваться для получения быстрой аппроксимации для  линейных программ, даже если эти программы могут быть решены точно при помощи LP-алгоритмов. Многие алгоритмы аппроксимации основаны на округлении решения таких программ, так что при необходимости можно решить нужные задачи приближенно (в этом случае общий коэффициент аппроксимации поглощает коэффициент аппроксимации LP-решения), зато более эффективно. \упоминаемых здесь два примера подобного подхода были приведены в работе [7].

Теоремы 1 и 2 можно применить для улучшения времени выполнения алгоритма Ленстры, Шмойса и Тардош [ ] для планирования несвязанных параллельных машин без вытеснения (RjjCmax): Пусть N заданий нужно спланировать для M машин, чтобы каждое задание i было включено в план ровно для одной машины j с временем обработки pij, так, чтобы совокупное время обработки по всем машинам было минимальным. Тогда для любого фиксированного r > 1 существует детерминированный алгоритм (1 + r)-аппроксимации, выполняющийся за время O(M2N log2 N log M), и рандомизированная версия, выполняющаяся за ожидаемое время O(MN log M log N). Для версии задачи с вытеснением существуют схемы аппроксимации с полиномиальным временем выполнения, требующие O(MN2log2N) времени и O(MNlogNlogM) ожидаемого времени для детерминированного и рандомизированного случая, соответственно.

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