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

Фактически нам необходима только ''приближенная'' версия PACK_ORACLE. Пусть <math>C_{\rho}(y) \;</math> – минимальная стоимость <math>y^T Ax \;</math>, достигаемая алгоритмом PACK_ORACLE для заданного y.

'''Теорема 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_{\rho}(y) + (\varepsilon / 2) \lambda y^T b</math>, где X минимально, так что неравенство <math>Ax \le \lambda b</math> удовлетворяется на текущей итерации x. Тогда теоремы 1 и 2 по-прежнему верны.'''

   

Время выполнения этих алгоритмов пропорционально ширине p; авторами статьи были разработаны техники уменьшения ширины для множества специальных случаев рассматриваемых задач. В качестве результата, полученного при помощи этих техник, можно привести следующий пример. Если задача об упаковке определяется при помощи выпуклого множества, являющегося произведением k выпуклых множеств меньших размерностей, т.е. P = P1 x • • • x Pk, и неравенств PlAlxl < b, тогда существует рандомизированная "-ослабленная разрешающая процедура, предположительно использующая O(s~2 k\og(ms~1) + klog k) вызовов подпрограммы, вычисляющей точку с минимальной стоимостью в P = {x € P : Alx l bg;l = 1... k, и детерминированная версия процедуры, использующая O{e~2k2 log(m£~1)) таких вызовов плюс время, необходимое для вычисления Ax для текущего компонента итерации x между последовательными вызовами. Этот результат может быть применен к задаче управления несколькими товарными потоками, при этом указанная подпрограмма должна выполнять вычисление потоков минимальной стоимости с одним источником, а не вычисление кратчайших путей, которое требуется для исходного алгоритма.

== Применение ==