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

'''Теорема 2. Для <math>0 < \varepsilon \le 1 \;</math> существует рандомизированная <math>\varepsilon \;</math>-ослабленная разрешающая процедура для дробно-линейной задачи упаковки, предположительно использующая <math>O(\varepsilon^{-2} (\sum_l \rho^l) \; log(m \varepsilon^{-1}) + k \; log(\rho \varepsilon^{-1}))</math> вызовов оракула PACK_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> между последовательными вызовами.'''