4446
правок
Дробно-линейные задачи об упаковке и покрытии: различия между версиями
Материал из WEGA
Дробно-линейные задачи об упаковке и покрытии (посмотреть исходный код)
Версия от 11:14, 16 ноября 2018
, 16 ноября 2018→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 74: | Строка 74: | ||
Фактически нам необходима только ''приближенная'' версия PACK_ORACLE. Пусть <math>C_{\rho}(y) \;< | Фактически нам необходима только ''приближенная'' версия PACK_ORACLE. Пусть <math>C_{\rho}(y) \;</math> – минимальная стоимость <math>y^T Ax \;</math>, достигаемая алгоритмом PACK_ORACLE для заданного y. | ||
<math>< | <math></math> | ||
Теорема 3. Заменим PACK_ORACLE на оракула, который для заданного вектора y > 0 находит точку x € P, такую, что yTAx < (1 + "/2)CP(y) + {el2)Xyrb, где X минимально, так что неравенство Ax < Xb удовлетворяется на текущей итерации x. Тогда теоремы 1 и 2 по-прежнему верны. | Теорема 3. Заменим PACK_ORACLE на оракула, который для заданного вектора y > 0 находит точку x € P, такую, что yTAx < (1 + "/2)CP(y) + {el2)Xyrb, где X минимально, так что неравенство Ax < Xb удовлетворяется на текущей итерации x. Тогда теоремы 1 и 2 по-прежнему верны. | ||
