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

Перейти к навигации Перейти к поиску
Строка 48: Строка 48:
Время выполнения разработанных алгоритмов полиномиально зависит от <math>\varepsilon^{-1} \;</math> для любого параметра ошибки <math>\varepsilon > 0 \;</math>, а также от ''ширины'' <math>\rho \;</math> выпуклого множества P, относящегося к множеству неравенств <math>Ax \le b \;</math> или <math>Ax \ge b \;</math>, определяющему решаемую задачу. Более точно ширина <math>\rho \;</math> определяется следующим образом для каждой из рассматриваемых задач:
Время выполнения разработанных алгоритмов полиномиально зависит от <math>\varepsilon^{-1} \;</math> для любого параметра ошибки <math>\varepsilon > 0 \;</math>, а также от ''ширины'' <math>\rho \;</math> выпуклого множества P, относящегося к множеству неравенств <math>Ax \le b \;</math> или <math>Ax \ge b \;</math>, определяющему решаемую задачу. Более точно ширина <math>\rho \;</math> определяется следующим образом для каждой из рассматриваемых задач:


• PACKING (упаковка): p := maxi max x2P abi
• PACKING: <math>\rho := max_i \; max_{x \in P} \frac{a_i x}{b_i}</math>


• RELAXED PACKING (упаковка с ослабленными ограничениями): p := maxi maxx2P ^.
• RELAXED PACKING: <math>\hat{\rho} := max_i \; max_{x \in \hat{P}} \frac{a_i x}{b_i}</math>


• COVERING (покрытие): p := maxi maxx2P abi
• COVERING: <math>\rho := max_i \; max_{x \in P} \frac{a_i x}{b_i}</math>


• SIMULTANEOUS PACKING AND COVERING (одновременные упаковка и покрытие): := r maxfmaxi ^, max, + 1, где d
• SIMULTANEOUS PACKING AND COVERING: <math>\rho := max_{x \in P} \; max \{ max_i \frac{a_i x}{b_i}, max_i \frac{\hat{a}_i x}{\hat{b}_i} \}</math>


• GENERAL (общая задача): p := maxi  maxx2P jaix . bij+1 – вышеупомянутый вектор отклонения.
• GENERAL: <math>\rho := max_i \; max_{x \in P} \frac{|a_i x - b_i|}{d_i} + 1</math>, где d – вышеупомянутый вектор отклонения.


== Основные результаты ==
== Основные результаты ==
4551

правка

Навигация