4551
правка
Дробно-линейные задачи об упаковке и покрытии: различия между версиями
Перейти к навигации
Перейти к поиску
м
Дробно-линейные задачи об упаковке и покрытии (посмотреть исходный код)
Версия от 13:40, 5 октября 2018
, 5 октября 2018→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 62: | Строка 62: | ||
Теорема 1. Для <math>0 < \varepsilon \le 1 \;</math> существует детерминированная <math>\varepsilon \;</math>-ослабленная разрешающая процедура для дробно-линейной задачи упаковки, использующая O( | '''Теорема 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 записывается в виде произведения политопов меньшей размерности, т.е. P = P'x'"XP', где каждый политоп Pl имеет ширину p (очевидно, что p < Pl fl), и имеется отдельный PACK_ORACLE для каждого Pl ;Al, тогда рандомизация может использоваться для потенциального ускорения работы алгоритма. Обозначив за PACK_ORACLEl оракул для Pl; Al, получаем следующий результат: | Для случая, когда P записывается в виде произведения политопов меньшей размерности, т.е. P = P'x'"XP', где каждый политоп Pl имеет ширину p (очевидно, что p < Pl fl), и имеется отдельный PACK_ORACLE для каждого Pl ;Al, тогда рандомизация может использоваться для потенциального ускорения работы алгоритма. Обозначив за PACK_ORACLEl оракул для Pl; Al, получаем следующий результат: | ||