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

Для случая, когда P записывается в виде произведения политопов меньшей размерности, т. е. <math>P = P^1 \times ... \times P^k</math>, где каждый политоп <math>P^l \;</math> имеет ширину <math>\rho^l \;</math> (очевидно, что <math>\rho \le \sum_l \rho^l</math>), и имеется отдельный оракул PACK_ORACLE для каждого <math>P^l, A^l \;</math>, тогда рандомизация может использоваться для потенциального ускорения работы алгоритма. Обозначив за PACK_ORACLEl оракул для <math>P^l, A^l \;</math>, получаем следующий результат:

Теорема 2. Для 0 < " < 1 существует рандомизированная "-ослабленная разрешающая процедура для дробно-линейной задачи упаковки, предположительно использующая O{e~2(^2l pl)\og{me~l) + /clog(p£~1)) вызовов оракула PACK_ORACLEL для некоторого l 2 f1. kg (возможно, l различно для каждого вызова) плюс время, необходимое для вычисления Pl Al xl для текущего компонента итерации x = (x1 ,x2,..;   xk) между последовательными вызовами.