4446
правок
Дробно-линейные задачи об упаковке и покрытии: различия между версиями
Перейти к навигации
Перейти к поиску
Дробно-линейные задачи об упаковке и покрытии (посмотреть исходный код)
Версия от 12:20, 30 ноября 2018
, 30 ноября 2018нет описания правки
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) Нет описания правки Метка: очистка |
||
| Строка 113: | Строка 113: | ||
== Применение == | == Применение == | ||
Представленные выше результаты могут использоваться для получения быстрой аппроксимации для линейных программ, даже если эти программы могут быть решены точно при помощи 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). | |||
== Открытые вопросы == | |||
Основным открытым вопросом является дальнейшее сокращение времени выполнения приближенных решений различных дробно-линейных задач. Одно потенциальное направление заключается в улучшении границ для конкретных задач, что было успешно проделано для задачи управления несколькими товарными потоками в серии статей, начатой работой Шарохи и Матулы [8]. Из той же отправной точки вышла серия результатов Григориадиса и Хачияна, независимо разработанных с [ ], начиная с работы [ ], в которой представлен алгоритм с числом вызовов, меньшим чем в теореме 1 на коэффициент log(m£~1)/log m. Значительные усилия были направлены на сокращение зависимости времени выполнения от ширины задачи или на уменьшение самой ширины (см, например, последовательные и параллельные алгоритмы для смешанной задачи упаковки и покрытия в [9]), так что это тоже может быть перспективным направлением для улучшения. | |||
Остается открытой задача из [ ] по разработке схем аппроксимации для модели RAM, использующих только полилогарифмические по длине входных данных точность и работу для общего случая рассматриваемых задач. | |||
== См. также == | |||
* [[Минимальный период обработки на несвязанных машинах]] | |||
== Литература == | |||
1. Grigoriadis, M.D., Khachiyan, L.G.: Fast approximation schemes for convex programs with many blocks and coupling constraints. SIAM J. Optim. 4,86-107 (1994) | |||
2. Held, M., Karp, R.M.: The traveling-salesman problem and minimum cost spanning trees. Oper. Res. 18,1138-1162 (1970) | |||
3. Karger, D.R., Stein, C.: An 6(n2) algorithm for minimum cut. In: Proceeding of 25th Annual ACM Symposium on Theory of Computing (STOC), 1993, pp. 757-765 | |||
4. Leighton, F.T., Makedon, F., Plotkin, S.A., Stein, C., Tardos, Ё., Tragoudas, S.: Fast approximation algorithms for multicommodity flow problems. J. Comp. Syst. Sci. 50(2), 228-243 (1995) | |||
5. Lenstra, J.K., Shmoys, D.B., Tardos, Ё.: Approximation algorithms for scheduling unrelated parallel machines. Math. Program. Ser. A 24, 259-272 (1990) | |||
6. Plotkin, S.A., Shmoys, D.B., Tardos, Ё.: Fast approximation algorithms for fractional packing and covering problems. In: Proceedings of 32nd Annual IEEE Symposium on Foundations of Computer Science (FOCS), 1991, pp.495-504 | |||
7. Plotkin, S.A., Shmoys, D.B., Tardos, Ё.: Fast approximation algorithms for fractional packing and covering problems. Math. Oper. Res. 20(2) 257-301 (1995). Preliminary version appeared in [6] | |||
8. Shahrokhi, F., Matula, D.W.: The maximum concurrent flow problem. J. ACM 37, 318-334(1990) | |||
9. Young, N.E.: Sequential and parallel algorithms for mixed packing and covering. In: Proceedings of 42nd Annual IEEE Symposium on Foundations of Computer Science (FOCS), 2001, pp.538-546 | |||