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

'''Теорема 1. Для <math>0 < \varepsilon \le 1 \;</math> существует детерминированная <math>\varepsilon \;</math>-ослабленная разрешающая процедура для дробно-линейной задачи упаковки, использующая <math>O(\varepsilon^{-2} \rho \; log(m \varepsilon^{-1}))</math> вызовов оракула PACK_ORACLE плюс время, необходимое для вычисления Ax для текущего компонента итерации x между последовательными вызовами.'''

 

Для случая, когда 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>, получаем следующий результат: