4488
правок
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
Строка 107: | Строка 107: | ||
Теорема 8. Для 0 < | '''Теорема 8. Для <math>0 < \varepsilon \le 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>\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 между последовательными вызовами. Этот результат может быть применен к задаче управления несколькими товарными потоками, при этом указанная подпрограмма должна выполнять вычисление потоков минимальной стоимости с одним источником, а не вычисление кратчайших путей, которое требуется для исходного алгоритма. | ||
== Применение == | == Применение == |
правок