4446
правок
Дробно-линейные задачи об упаковке и покрытии: различия между версиями
Материал из WEGA
Дробно-линейные задачи об упаковке и покрытии (посмотреть исходный код)
Версия от 13:52, 5 октября 2018
, 5 октября 2018→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 68: | Строка 68: | ||
'''Теорема 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> между последовательными вызовами.''' | '''Теорема 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> между последовательными вызовами.''' | ||
Теорема 2 также выполняется для задачи RELAXED PACKING, если заменить <math>\rho \;</math> на <math>\hat{\rho}</math>, а PACK_ORACLE – на REL_PACK_ORACLE. | Теорема 2 также выполняется для задачи RELAXED PACKING, если заменить <math>\rho \;</math> на <math>\hat{\rho}</math>, а PACK_ORACLE – на REL_PACK_ORACLE. | ||
