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

В данной статье приводится обзор быстрых алгоритмов, дающих приближенные решения для задач, которые могут быть сформулированы в виде задач линейного программирования (LP) и, следовательно, могут быть решено точно, хотя это потребует большего времени выполнения. Общий формат семейства таких задач имеет следующий вид. Дано множество из m неравенств с n переменными и оракул, который выдает решение подходящей задачи оптимизации над выпуклым множеством <math>P \in \mathbb{R}^n</math>. Найти решение <math>x \in P \;</math>, удовлетворяющее неравенствам, или обнаружить, что такого решения x не существует. Принципиальная идея алгоритма заключается в следующем. Алгоритм всегда начинает работу с недопустимого решения x и использует оракул оптимизации для поиска направления, в котором степень нарушения неравенств может быть уменьшена; это выполняется при помощи расчета вектора y, представляющего собой ''решение двойственной задачи относительно x''. После этого x аккуратно изменяется в этом направлении, и процесс повторяется до тех пор, пока x не становится «приближенно» допустимым. Далее будут рассмотрены конкретные задачи и соответствующие им оракулы оптимизации, а также определены другие нотации используемой «аппроксимации».

PACKING (упаковка): Даны матрица 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>?

RELAXED PACKING (упаковка с ослабленными ограничениями): Даны <math>\varepsilon > 0 \;</math>, матрица A размера <math>m \times n</math>, b > 0 и выпуклые множества <math>P \in \mathbb{R}^n</math> и <math>\hat{P} \in \mathbb{R}^n</math>, такие, что <math>P \subseteq \hat{P}</math> и <math>Ax \ge 0, \forall x \in P</math>. Найти такое <math>x \in \hat{P}</math>, что <math>Ax \le (1 + \varepsilon)b \;</math>, или показать, что <math>\nexists x \in P</math>, такого, что <math>Ax \le b \;</math>.

REL_PACK_ORACLE (оракул упаковки с ослабленными ограничениями): Даны m-мерный вектор <math>y \ge 0 \;</math> и вышеописанные множества <math>P, \hat{P}</math>. Вернуть <math>\bar{x} \in \hat{P}</math>, такое, что <math>y^T Ax \le min \{y^T Ax : x \in P \}</math>.