4446
правок
Дробно-линейные задачи об упаковке и покрытии: различия между версиями
Перейти к навигации
Перейти к поиску
Дробно-линейные задачи об упаковке и покрытии (посмотреть исходный код)
Версия от 11:41, 16 ноября 2018
, 16 ноября 2018→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 86: | Строка 86: | ||
Теорема 4. Для 0 < | '''Теорема 4. Для <math>0 < \varepsilon < 1 \;</math> существует детерминированная <math>\varepsilon</math>-ослабленная разрешающая процедура для дробно-линейной задачи о покрытии, использующая <math>O(m + \rho \; log^2 \; m + \varepsilon^{-2} \rho \; log(m \varepsilon^{-1}))</math> вызовов оракула COVER_ORACLE плюс время, необходимое для вычисления Ax для текущего компонента итерации x между последовательными вызовами.''' | ||
'''Теорема 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> между последовательными вызовами.''' | |||
Пусть CC(y) – максимальная стоимость cost yTAx, достигаемая алгоритмом COVER_ORACLE для заданного y. | Пусть CC(y) – максимальная стоимость cost yTAx, достигаемая алгоритмом COVER_ORACLE для заданного y. | ||