4551
правка
Дробно-линейные задачи об упаковке и покрытии: различия между версиями
Перейти к навигации
Перейти к поиску
м
Дробно-линейные задачи об упаковке и покрытии (посмотреть исходный код)
Версия от 11:13, 16 ноября 2018
, 16 ноября 2018→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 74: | Строка 74: | ||
Фактически нам необходима только приближенная версия PACK_ORACLE. Пусть | Фактически нам необходима только ''приближенная'' версия PACK_ORACLE. Пусть <math>C_{\rho}(y) \;<\math> – минимальная стоимость <math>y^T Ax \;<\math>, достигаемая алгоритмом PACK_ORACLE для заданного y. | ||
<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 по-прежнему верны. | ||