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

'''Теорема 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 по-прежнему верны.'''

Теорема 3 говорит о том, что даже если не существует эффективной реализации оракула, как, например, в случае, когда оракул NP-полную задачу, достаточно будет полностью полиномиальной схемы аппроксимации.

'''Теорема 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> (возможно, l различно для каждого вызова) плюс время, необходимое для вычисления <math>\sum_l A^l x^l</math> для текущего компонента итерации <math>x = (x^1, x^2, ..., x^k)</math> между последовательными вызовами.'''

Обозначим за <math>C_c(y)</math> максимальную стоимость <math>y^T Ax</math>, достигаемую алгоритмом COVER_ORACLE для заданного y.