4551
правка
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 по-прежнему верны. | ||
правка