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

COVERING (покрытие): Даны матрица A размера <math>m \times n</math>, b > 0 и выпуклое множество <math>P \in \mathbb{R}^n</math>, такое, что <math>Ax \ge 0, \forall x \in P</math>. Существует ли такое <math>x \in P \;</math>, что <math>Ax \le b \;</math>?

SIMULTANEOUS PACKING AND COVERING (одновременные упаковка и покрытие): Даны матрицы <math>\hat{A}</math> и <math>A \;</math> размера <math>\hat{m} \times n</math> и <math>(m - \hat{m}) \times n</math>, соответственно, <math>b > 0 \;</math> и <math>\hat{b} > 0 \;</math>, а также выпуклое множество <math>P \in \mathbb{R}^n</math>, такое, что <math>Ax \ge 0, \hat{A}x \ge 0, \forall x \in P</math>. Существует ли такое <math>x \in P \;</math>, что <math>Ax \le b \;</math> и <math>\hat{A}x \ge \hat{b}</math>?

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

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

'''Теорема 3. Заменим PACK_ORACLE на оракула, который для заданного вектора <math>y \ge 0 \;</math> находит точку <math>\bar{x} \in P</math>, такую, что <math>y^T A \bar{x} \le (1 + \varepsilon/2) C_{\rho}(y) + (\varepsilon / 2) \lambda y^T b</math>, где X минимально, так что неравенство <math>Ax \le \lambda b</math> удовлетворяется на текущей итерации x. Тогда теоремы 1 и 2 по-прежнему верны.'''

Теорема 3 говорит о том, что даже если не существует эффективной реализации оракула, как, например, в случае, когда оракул NP-полную задачу, достаточно будет полностью полиномиальной схемы аппроксимации.

'''Теорема 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> между последовательными вызовами.'''

Обозначим за <math>C_c(y)</math> максимальную стоимость <math>y^T Ax</math>, достигаемую алгоритмом COVER_ORACLE для заданного y.

'''Теорема 6. Заменим COVER_ORACLE на оракула, который для заданного вектора <math>y \ge 0</math> находит точку <math>\bar{x} \in P</math>, такую, что <math>y^T \bar{x} \ge (1 - \varepsilon/2) C_C(y) - (\varepsilon/2) \lambda y^T b</math>, где <math>\lambda</math> максимально, так что неравенство <math>Ax \ge \lambda b</math> удовлетворяется на текущей итерации x. Тогда теоремы 4 и 5 по-прежнему верны.'''

'''Теорема 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 между последовательными вызовами.'''

'''Теорема 8. Для <math>0 < \varepsilon \le 1</math> существует детерминированная <math>\varepsilon</math>-ослабленная разрешающая процедура для общей задачи, использующая <math>O(\varepsilon^{-2} \rho^2 \; log(m \; \rho \; \varepsilon^{-1}))</math> вызовов оракула GEN_ORACLE плюс время, необходимое для вычисления Ax для текущего компонента итерации x между последовательными вызовами.'''

Время выполнения этих алгоритмов пропорционально ширине <math>\rho</math>; авторами статьи были разработаны техники уменьшения ширины для множества специальных случаев рассматриваемых задач. В качестве результата, полученного при помощи этих техник, можно привести следующий пример. Если задача об упаковке определяется при помощи выпуклого множества, являющегося произведением k выпуклых множеств меньших размерностей, т. е. <math>P = P^1 \times \cdot \cdot \cdot \times P^k</math>, и неравенств <math>\sum_l A^l x^l \le b</math>, тогда существует рандомизированная <math>\varepsilon</math>-ослабленная разрешающая процедура, предположительно использующая <math>O(\varepsilon^{-2} k \; log(m \; \varepsilon^{-1}) + k \; log \; k)</math> вызовов подпрограммы, вычисляющей точку с минимальной стоимостью в <math>\hat{P}^l = \{ x^l \in P^l: A^l x^l \le b \}, l = 1, ..., k</math>, и детерминированная версия процедуры, использующая <math>O(\varepsilon^{-2} \; k^2 \; log(m \; \varepsilon^{-1}))</math> таких вызовов плюс время, необходимое для вычисления Ax для текущего компонента итерации x между последовательными вызовами. Этот результат может быть применен к задаче управления несколькими товарными потоками, при этом указанная подпрограмма должна выполнять вычисление потоков минимальной стоимости с одним источником, а не вычисление кратчайших путей, которое требуется для исходного алгоритма.

Представленные выше результаты могут использоваться для получения быстрой аппроксимации для  линейных программ, даже если эти программы могут быть решены точно при помощи LP-алгоритмов. Многие алгоритмы аппроксимации основаны на округлении решения таких программ, так что при необходимости можно решить нужные задачи приближенно (в этом случае общий коэффициент аппроксимации поглощает коэффициент аппроксимации LP-решения), зато более эффективно. Упоминаемые здесь два примера подобного подхода были приведены в работе [7].

Теоремы 1 и 2 можно применить для улучшения времени выполнения алгоритма Ленстры, Шмойса и Тардош [5] для планирования несвязанных параллельных машин без вытеснения <math>(R||C_{max})</math>. Пусть N заданий нужно спланировать для M машин, чтобы каждое задание i было включено в план ровно для одной машины j с временем обработки <math>p_{ij}</math>, так, чтобы совокупное время обработки по всем машинам было минимальным. Тогда для любого фиксированного r > 1 существует детерминированный алгоритм (1 + r)-аппроксимации, выполняющийся за время <math>O(M^2N \; log^2 N \; log \; M)</math>, и рандомизированная версия, выполняющаяся за ожидаемое время <math>O(M N \; log \; M \; log \; N)</math>. Для версии задачи с вытеснением существуют схемы аппроксимации с полиномиальным временем выполнения, требующие <math>O(M N^2 log^2 N)</math> времени и <math>O(M N \; log \; N \; log \; M)</math> ожидаемого времени для детерминированного и рандомизированного случая, соответственно.

Для метрической задачи коммивояжера для N вершин хорошо известна граница Хельда-Карпа [2], которую можно представить как оптимум линейной программы над ''политопом с удалением подциклов''. Используя рандомизированный алгоритм нахождения минимального разреза Каргера и Штейна [3], можно получить рандомизированную схему аппроксимации, вычисляющую границу Хельда-Карпа за ожидаемое время <math>O(N^4 \; log^6 N)</math>.

Основным открытым вопросом является дальнейшее сокращение времени выполнения приближенных решений различных дробно-линейных задач. Одно потенциальное направление заключается в улучшении границ для конкретных задач, что было успешно проделано для задачи управления несколькими товарными потоками в серии статей, начатой работой Шарохи и Матулы [8]. Из той же отправной точки вышла серия результатов Григориадиса и Хачияна, независимо разработанных для [7], начиная с работы [1], в которой представлен алгоритм с числом вызовов, меньшим чем в теореме 1 на коэффициент <math>log(m \varepsilon^{-1})/log \; m</math>. Значительные усилия были направлены на сокращение зависимости времени выполнения от ширины задачи или на уменьшение самой ширины (см, например, последовательные и параллельные алгоритмы для смешанной задачи упаковки и покрытия в [9]), так что это тоже может быть перспективным направлением для улучшения.

Остается открытой задача из [7] по разработке схем аппроксимации для модели RAM, использующих только ''полилогарифмические по длине входных данных'' точность и работу для общего случая рассматриваемых задач.