4446
правок
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) мНет описания правки |
||
(не показано 5 промежуточных версий этого же участника) | |||
Строка 78: | Строка 78: | ||
'''Теорема 3. Заменим PACK_ORACLE на оракула, который для заданного вектора <math>y \ge 0 \;</math> находит точку <math>\bar{x} \in P</math>, такую, что <math>y^T A \bar{x} \le (1 + \varepsilon/2) C_{\ | '''Теорема 3. Заменим PACK_ORACLE на оракула, который для заданного вектора <math>y \ge 0 \;</math> находит точку <math>\bar{x} \in P</math>, такую, что <math>y^T A \bar{x} \le (1 + \varepsilon/2) C_{\mathcal{P}}(y) + (\varepsilon / 2) \lambda y^T b</math>, где <math>\lambda</math> – такое минимальное число, что неравенство <math>Ax \le \lambda b</math> удовлетворяется на текущей итерации x. Тогда теоремы 1 и 2 по-прежнему верны.''' | ||
Теорема 3 говорит о том, что даже если не существует эффективной реализации оракула, как, например, в случае, когда оракул NP-полную задачу, достаточно будет полностью полиномиальной схемы | Теорема 3 говорит о том, что даже если не существует эффективной реализации оракула, как, например, в случае, когда оракул решает NP-полную задачу, достаточно будет полностью полиномиальной аппроксимационной схемы. | ||
Строка 90: | Строка 90: | ||
'''Теорема 5. Для <math>0 < \varepsilon < 1</math> существует рандомизированная <math>\varepsilon</math>-ослабленная разрешающая процедура для дробно-линейной задачи о покрытии, предположительно использующая <math>O(mk + (\sum_l \rho^l)log^2 | '''Теорема 5. Для <math>0 < \varepsilon < 1</math> существует рандомизированная <math>\varepsilon</math>-ослабленная разрешающая процедура для дробно-линейной задачи о покрытии, предположительно использующая <math>O(mk + (\sum_l \rho^l)log^2 m + k \; log \varepsilon^{-1} + \varepsilon^{-2} (\sum_l \rho^l) log(m \varepsilon^{-1}))</math> вызовов оракула COVER_ORACLE<math>_l</math> для некоторого <math>l \in \{ 1, ..., k \}</math> (возможно, <math>l</math> различно для каждого вызова) плюс время, необходимое для вычисления <math>\sum_l A^l x^l</math> для текущего компонента итерации <math>x = (x^1, x^2, ..., x^k)</math> между последовательными вызовами.''' | ||
Обозначим за <math> | Обозначим за <math>C_C(y)</math> максимальную стоимость <math>y^T Ax</math>, достигаемую алгоритмом COVER_ORACLE для заданного y. | ||
'''Теорема 6. Заменим COVER_ORACLE на оракула, который для заданного вектора <math>y \ge 0</math> находит точку <math>\bar{x} \in P</math>, такую, что <math>y^T \bar{x} \ge (1 - \varepsilon/2) C_C(y) - (\varepsilon/2) \lambda y^T b</math>, где <math>\lambda</math> | '''Теорема 6. Заменим COVER_ORACLE на оракула, который для заданного вектора <math>y \ge 0</math> находит точку <math>\bar{x} \in P</math>, такую, что <math>y^T \bar{x} \ge (1 - \varepsilon/2) C_C(y) - (\varepsilon/2) \lambda y^T b</math>, где <math>\lambda</math> – такое максимальное число, что неравенство <math>Ax \ge \lambda b</math> удовлетворяется на текущей итерации x. Тогда теоремы 4 и 5 по-прежнему верны.''' | ||
Строка 102: | Строка 102: | ||
'''Теорема 7. Для <math>0 < \varepsilon \le 1</math> существуют рандомизированная <math>\varepsilon</math>-ослабленная разрешающая процедура для дробно-линейной задачи одновременных упаковке и покрытии, предположительно использующая <math>O(m^2 (log^2 \rho) \varepsilon^{-2} \; log(\varepsilon^{-1} m \; log \; \rho))</math> вызовов оракула SIM_ORACLE, и детерминированная версия, использующая на <math>log \; \rho</math> вызовов больше, плюс время, необходимое для вычисления <math>\hat{A}x</math> для текущего компонента итерации x между последовательными вызовами.''' | '''Теорема 7. Для <math>0 < \varepsilon \le 1</math> существуют рандомизированная <math>\varepsilon</math>-ослабленная разрешающая процедура для дробно-линейной задачи об одновременных упаковке и покрытии, предположительно использующая <math>O(m^2 (log^2 \rho) \varepsilon^{-2} \; log(\varepsilon^{-1} m \; log \; \rho))</math> вызовов оракула SIM_ORACLE, и детерминированная версия, использующая на <math>log \; \rho</math> вызовов больше, плюс время, необходимое для вычисления <math>\hat{A}x</math> для текущего компонента итерации x между последовательными вызовами.''' | ||
Строка 108: | Строка 108: | ||
'''Теорема 8. Для <math>0 < \varepsilon | '''Теорема 8. Для <math>0 < \varepsilon < 1</math> существует детерминированная <math>\varepsilon</math>-ослабленная разрешающая процедура для общей задачи, использующая <math>O(\varepsilon^{-2} \rho^2 \; log(m \; \rho \; \varepsilon^{-1}))</math> вызовов оракула GEN_ORACLE плюс время, необходимое для вычисления Ax для текущего компонента итерации x между последовательными вызовами.''' | ||
Время выполнения этих алгоритмов пропорционально ширине <math>\rho</math>; авторами статьи были разработаны техники уменьшения ширины для множества специальных случаев рассматриваемых задач. В качестве результата, полученного при помощи этих техник, можно привести следующий пример. Если задача об упаковке определяется при помощи выпуклого множества, являющегося произведением k выпуклых множеств меньших размерностей, т. е. <math>P = P^1 \times \cdot \cdot \cdot \times P^k</math>, и неравенств <math>\sum_l A^l x^l \le b</math>, тогда | Время выполнения этих алгоритмов пропорционально ширине <math>\rho</math>; авторами статьи были разработаны техники уменьшения ширины для множества специальных случаев рассматриваемых задач. В качестве результата, полученного при помощи этих техник, можно привести следующий пример. Если задача об упаковке определяется при помощи выпуклого множества, являющегося произведением k выпуклых множеств меньших размерностей, т. е. <math>P = P^1 \times \cdot \cdot \cdot \times P^k</math>, и неравенств <math>\sum_l A^l x^l \le b</math>, тогда существуют рандомизированная <math>\varepsilon</math>-ослабленная разрешающая процедура, предположительно использующая <math>O(\varepsilon^{-2} k \; log(m \; \varepsilon^{-1}) + k \; log \; k)</math> вызовов подпрограммы, вычисляющей точку с минимальной стоимостью в <math>\hat{P}^l = \{ x^l \in P^l: A^l x^l \le b \}, l = 1, ..., k</math>, и детерминированная версия процедуры, использующая <math>O(\varepsilon^{-2} \; k^2 \; log(m \; \varepsilon^{-1}))</math> таких вызовов плюс время, необходимое для вычисления Ax для текущего компонента итерации x между последовательными вызовами. Этот результат может быть применен к задаче управления несколькими товарными потоками, при этом указанная подпрограмма должна выполнять вычисление потоков минимальной стоимости с одним источником, а не вычисление кратчайших путей, которое требуется для исходного алгоритма. | ||
== Применение == | == Применение == | ||
Представленные выше результаты могут использоваться для получения быстрой аппроксимации для линейных программ, даже если эти программы могут быть решены точно при помощи LP-алгоритмов. Многие алгоритмы | Представленные выше результаты могут использоваться для получения быстрой аппроксимации для линейных программ, даже если эти программы могут быть решены точно при помощи LP-алгоритмов. Многие аппроксимационные алгоритмы основаны на округлении решения таких программ, так что при необходимости можно решить нужные задачи приближенно (в этом случае общий коэффициент аппроксимации поглощает коэффициент аппроксимации LP-решения), зато более эффективно. Упоминаемые здесь два примера подобного подхода были приведены в работе [7]. | ||
Теоремы 1 и 2 можно применить для улучшения времени выполнения алгоритма Ленстры, Шмойса и Тардош [5] для планирования несвязанных параллельных машин без вытеснения <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>. Для версии задачи с вытеснением существуют схемы | Теоремы 1 и 2 можно применить для улучшения времени выполнения алгоритма Ленстры, Шмойса и Тардош [5] для планирования несвязанных параллельных машин без вытеснения <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], можно получить рандомизированную схему | Для [[Метрическая задача коммивояжера|метрической задачи коммивояжера]] для N вершин хорошо известна граница Хельда-Карпа [2], которую можно представить как оптимум линейной программы над ''политопом с удалением подциклов''. Используя рандомизированный алгоритм нахождения минимального разреза Каргера и Штейна [3], можно получить рандомизированную аппроксимационную схему, вычисляющую границу Хельда-Карпа за ожидаемое время <math>O(N^4 \; log^6 N)</math>. | ||
== Открытые вопросы == | == Открытые вопросы == | ||
Основным открытым вопросом является дальнейшее сокращение времени выполнения приближенных решений различных дробно-линейных задач. Одно потенциальное направление заключается в улучшении границ для конкретных задач, что было успешно проделано для задачи управления несколькими товарными потоками в серии статей, начатой работой Шарохи и Матулы [8]. Из той же отправной точки вышла серия результатов Григориадиса и Хачияна, независимо разработанных для [7], начиная с работы [1], в которой представлен алгоритм с числом вызовов, меньшим | Основным открытым вопросом является дальнейшее сокращение времени выполнения приближенных решений различных дробно-линейных задач. Одно потенциальное направление заключается в улучшении границ для конкретных задач, что было успешно проделано для задачи управления несколькими товарными потоками в серии статей, начатой работой Шарохи и Матулы [8]. Из той же отправной точки вышла серия результатов Григориадиса и Хачияна, независимо разработанных для [7], начиная с работы [1], в которой представлен алгоритм с числом вызовов, меньшим на коэффициент <math>log(m \varepsilon^{-1})/log \; m</math> по сравнению с теоремой 1. Значительные усилия были направлены на сокращение зависимости времени выполнения от ширины задачи или на уменьшение самой ширины (см, например, последовательные и параллельные алгоритмы для смешанной задачи упаковки и покрытия в [9]), так что это тоже может быть перспективным направлением для улучшения. | ||
Остается открытой задача из [7] по разработке схем | Остается открытой задача из [7] по разработке аппроксимационных схем для модели RAM, использующих только ''полилогарифмические по длине входных данных'' точность и работу для общего случая рассматриваемых задач. | ||
== См. также == | == См. также == |
правок