4551
правка
Дробно-линейные задачи об упаковке и покрытии: различия между версиями
Перейти к навигации
Перейти к поиску
Дробно-линейные задачи об упаковке и покрытии (посмотреть исходный код)
Версия от 13:39, 5 октября 2018
, 5 октября 2018→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 59: | Строка 59: | ||
== Основные результаты == | == Основные результаты == | ||
Многие из нижеприведенных результатов были представлены в работе [7], в которой рассматривалась модель вычислений с точной арифметикой на вещественных числах и возведением в степень, занимающим один шаг. Однако, как отмечали авторы [7], эти алгоритмы могут быть преобразованы для выполнения на RAM-модели с использованием подходящей операции возведения в степень, версии оракула, выдающего ''почти'' оптимальное решение, и ограничения на количество используемых чисел, полиномиальное относительно длины входных данных и аналогичное количеству чисел, используемых в точных алгоритмах линейного программирования. Однако они оставляют открытым вопрос построения <math>\varepsilon \;</math>-приближенных решений, использующих полилогарифмическую точность для общего случая рассматриваемых ими задач (что можно сделать, например, в задаче управления несколькими товарными потоками [4]). | |||
Теорема 1. Для <math>0 < \varepsilon \le 1 \;</math> существует детерминированная <math>\varepsilon \;</math>-ослабленная разрешающая процедура для дробно-линейной задачи упаковки, использующая O(e~2p\og(me~1)) вызовов оракула PACK_ORACLE плюс время, необходимое для вычисления Ax для текущего компонента итерации x между последовательными вызовами. | |||
Для случая, когда P записывается в виде произведения политопов меньшей размерности, т.е. P = P'x'"XP', где каждый политоп Pl имеет ширину p (очевидно, что p < Pl fl), и имеется отдельный PACK_ORACLE для каждого Pl ;Al, тогда рандомизация может использоваться для потенциального ускорения работы алгоритма. Обозначив за PACK_ORACLEl оракул для Pl; Al, получаем следующий результат: | |||
Теорема 2. Для 0 < " < 1 существует рандомизированная "-ослабленная разрешающая процедура для дробно-линейной задачи упаковки, предположительно использующая O{e~2(^2l pl)\og{me~l) + /clog(p£~1)) вызовов оракула PACK_ORACLEL для некоторого l 2 f1. kg (возможно, l различно для каждого вызова) плюс время, необходимое для вычисления Pl Al xl для текущего компонента итерации x = (x1 ,x2,..; xk) между последовательными вызовами. | |||
Теорема 2 также выполняется для задачи RELAXED PACKING, если заменить p на p, а PACK_ORACLE – на REL_PACK_ORACLE. | |||