Дробно-линейные задачи об упаковке и покрытии: различия между версиями

Многие из нижеприведенных результатов были представлены в работе [7], в которой рассматривалась модель вычислений с точной арифметикой на вещественных числах и возведением в степень, занимающим один шаг. Однако, как отмечали авторы [7], эти алгоритмы могут быть преобразованы для выполнения на RAM-модели с использованием подходящей операции возведения в степень, версии оракула, выдающего ''почти'' оптимальное решение, и ограничения на количество используемых чисел, полиномиальное относительно длины входных данных и аналогичное количеству чисел, используемых в точных алгоритмах линейного программирования. Однако они оставляют открытым вопрос построения <math>\varepsilon \;</math>-приближенных решений, использующих полилогарифмическую точность для общего случая рассматриваемых ими задач (что можно сделать, например, в задаче управления несколькими товарными потоками [4]).

Фактически нам необходима только ''приближенная'' версия PACK_ORACLE. Пусть <math>C_{\rho}(y) \;</math> – минимальная стоимость <math>y^T Ax \;</math>, достигаемая алгоритмом PACK_ORACLE для заданного y.