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

Для параметра ошибки <math>\varepsilon > x0 \;</math> точка <math>x \in P \;</math> является <math>\varepsilon \;</math>-''приближенным решением'' для дробно-линейной задачи упаковки (или покрытия), если <math>Ax \le (1 + \varepsilon) \; b</math> (или <math>Ax \ge (1 - \varepsilon) \; b</math>, соответственно). С другой стороны, если <math>x \in P \;</math> удовлетворяет условию <math>Ax \le b \;</math> (или <math>Ax \ge b) \;</math>, то x ''является точным решением''. Для общей задачи GENERAL, параметра ошибки <math>\varepsilon > 0 \;</math> и положительного вектора отклонения d значение <math>x \in P \;</math> является <math>\varepsilon \;</math>-''приближенным решением'', если <math>Ax \le b + \varepsilon \; d</math>, и ''точным решением'', если <math>Ax \le b \;</math>. <math>\varepsilon \;</math>-ослабленная разрешающая процедура для этих задач либо находит "-приближенное решение, либо обоснованно сообщает о том, что точного решения не существует. В общем случае в задаче минимизации (максимизации) алгоритм <math>(1 + \varepsilon) \;</math>-аппроксимации (<math>(1 - \varepsilon) \;</math>-аппроксимации) возвращает значение, не более чем в <math>(1 + \varepsilon) \;</math> (не менее чем в (1 - \varepsilon) \;) раз отличающееся от оптимального.

Время выполнения разработанных алгоритмов полиномиально зависит от e"1 для любого параметра ошибки " > 0, а также от ширины p выпуклого множества P, родственного множеству неравенств Ax < b или Ax > b, определяющему решаемую задачу. Более точно ширина p определяется следующим образом для каждой из рассматриваемых задач: