4551
правка
Дробно-линейные задачи об упаковке и покрытии: различия между версиями
Перейти к навигации
Перейти к поиску
Дробно-линейные задачи об упаковке и покрытии (посмотреть исходный код)
Версия от 14:17, 16 ноября 2018
, 16 ноября 2018→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 101: | Строка 101: | ||
Теорема 7. Для 0 < | '''Теорема 7. Для <math>0 < \varepsilon \le 1</math> существуют рандомизированная <math>\varepsilon</math>-ослабленная разрешающая процедура для дробно-линейной задачи одновременных упаковке и покрытии, предположительно использующая <math>O(m^2 (log^2 \rho) \varepsilon^{-2} \; log(\varepsilon^{-1} m \; log \; \rho))</math> вызовов оракула SIM_ORACLE, и детерминированная версия, использующая на <math>log \; \rho</math> вызовов больше, плюс время, необходимое для вычисления <math>\hat{A}x</math> для текущего компонента итерации x между последовательными вызовами.''' | ||