4446
правок
Дробно-линейные задачи об упаковке и покрытии: различия между версиями
Материал из WEGA
Дробно-линейные задачи об упаковке и покрытии (посмотреть исходный код)
Версия от 12:52, 5 октября 2018
, 5 октября 2018→Постановка задачи
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 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 | • PACKING: <math>\rho := max_i \; max_{x \in P} \frac{a_i x}{b_i}</math> | ||
• RELAXED PACKING | • RELAXED PACKING: <math>\hat{\rho} := max_i \; max_{x \in \hat{P}} \frac{a_i x}{b_i}</math> | ||
• COVERING | • COVERING: <math>\rho := max_i \; max_{x \in P} \frac{a_i x}{b_i}</math> | ||
• SIMULTANEOUS PACKING AND COVERING | • 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 | • GENERAL: <math>\rho := max_i \; max_{x \in P} \frac{|a_i x - b_i|}{d_i} + 1</math>, где d – вышеупомянутый вектор отклонения. | ||
== Основные результаты == | == Основные результаты == | ||
