4446
правок
Дробно-линейные задачи об упаковке и покрытии: различия между версиями
Материал из WEGA
Дробно-линейные задачи об упаковке и покрытии (посмотреть исходный код)
Версия от 11:19, 16 ноября 2018
, 16 ноября 2018→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 77: | Строка 77: | ||
<math></math> | <math></math> | ||
Теорема 3. Заменим 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 по-прежнему верны.''' | ||
| Строка 83: | Строка 83: | ||
Схожие результаты можно доказать для дробно-линейной задачи о покрытии ( | Схожие результаты можно доказать для дробно-линейной задачи о покрытии (COVER_ORACLE<math>_l</math> определяется аналогично PACK_ORACLE<math>_l</math>): | ||
