4446
правок
Дробно-линейные задачи об упаковке и покрытии: различия между версиями
Материал из WEGA
Дробно-линейные задачи об упаковке и покрытии (посмотреть исходный код)
Версия от 11:10, 16 ноября 2018
, 16 ноября 2018→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 72: | Строка 72: | ||
Теорема 2 также выполняется для задачи RELAXED PACKING, если заменить <math>\rho \;</math> на <math>\hat{\rho}</math>, а PACK_ORACLE – на REL_PACK_ORACLE. | Теорема 2 также выполняется для задачи RELAXED PACKING, если заменить <math>\rho \;</math> на <math>\hat{\rho}</math>, а PACK_ORACLE – на REL_PACK_ORACLE. | ||
Фактически нам необходима только приближенная версия PACK_ORACLE. Пусть CP(y) – минимальная стоимость cost yTAx, достигаемая алгоритмом PACK_ORACLE для заданного y. | |||
Теорема 3. Заменим PACK_ORACLE на оракула, который для заданного вектора y > 0 находит точку x € P, такую, что yTAx < (1 + "/2)CP(y) + {el2)Xyrb, где X минимально, так что неравенство Ax < Xb удовлетворяется на текущей итерации x. Тогда теоремы 1 и 2 по-прежнему верны. | |||
Теорема 3 говорит о том, что даже если не существует эффективной реализации оракула, как, например, в случае, когда оракул NP-полную задачу, достаточно будет полностью полиномиальной схемы аппроксимации. | |||
Схожие результаты можно доказать для дробно-линейной задачи о покрытии (COVER_ORACLEl определяется аналогично PACK_ORACLEL): | |||
Теорема 4. Для 0 < " < 1 существует детерминированная "-ослабленная разрешающая процедура для дробно-линейной задачи о покрытии, использующая O(m + plog m + s~2p\og(ms~1)) вызовов оракула COVER_ORACLE плюс время, необходимое для вычисления Ax для текущего компонента итерации x между последовательными вызовами. | |||
Теорема 5. Для 0 < " < 1 существует рандомизированная "-ослабленная разрешающая процедура для дробно-линейной задачи о покрытии, предположительно использующая O(mk + Q^ p')log m+ k\oge~l + E~2(Hi P/)log(m£~1)) вызовов оракула COVER_ORACLEL для некоторого l 2 f1. kg (возможно, l различно для каждого вызова) плюс время, необходимое для вычисления Pl Al xl для текущего компонента итерации x = (x1 ,x2,..; xk) между последовательными вызовами. | |||
Пусть CC(y) – максимальная стоимость cost yTAx, достигаемая алгоритмом COVER_ORACLE для заданного y. | |||
Теорема 6. Заменим COVER_ORACLE на оракула, который для заданного вектора y > 0 находит точку x € P, такую, что yTAx > (1 — "/2)CC(y) — {el2)Xyrb, где X максимально, так что неравенство Ax > Xb удовлетворяется на текущей итерации x. Тогда теоремы 4 и 5 по-прежнему верны. | |||
Для задачи об одновременных упаковке и покрытии верно следующее: | |||
Теорема 7. Для 0 < " < 1 существуют рандомизированная "-ослабленная разрешающая процедура для дробно-линейной задачи одновременных упаковке и покрытии, предположительно использующая O(m2(log2p)£~2log(£~1mlogp)) вызовов оракула SIM_ORACLE, и детерминированная версия, использующая на oflog p вызовов больше, плюс время, необходимое для вычисления Ax для текущего компонента итерации x между последовательными вызовами. | |||
Для общей задачи GENERAL верно следующее: | |||
Теорема 8. Для 0 < " < 1 существует детерминированная "-ослабленная разрешающая процедура для общей задачи, использующая O(s~2p2 log(mp£~1)) вызовов оракула GEN_ORACLE плюс время, необходимое для вычисления Ax для текущего компонента итерации x между последовательными вызовами. | |||
Время выполнения этих алгоритмов пропорционально ширине p; авторами статьи были разработаны техники уменьшения ширины для множества специальных случаев рассматриваемых задач. В качестве результата, полученного при помощи этих техник, можно привести следующий пример. Если задача об упаковке определяется при помощи выпуклого множества, являющегося произведением k выпуклых множеств меньших размерностей, т.е. P = P1 x • • • x Pk, и неравенств PlAlxl < b, тогда существует рандомизированная "-ослабленная разрешающая процедура, предположительно использующая O(s~2 k\og(ms~1) + klog k) вызовов подпрограммы, вычисляющей точку с минимальной стоимостью в P = {x € P : Alx l bg;l = 1... k, и детерминированная версия процедуры, использующая O{e~2k2 log(m£~1)) таких вызовов плюс время, необходимое для вычисления Ax для текущего компонента итерации x между последовательными вызовами. Этот результат может быть применен к задаче управления несколькими товарными потоками, при этом указанная подпрограмма должна выполнять вычисление потоков минимальной стоимости с одним источником, а не вычисление кратчайших путей, которое требуется для исходного алгоритма. | |||
== Применение == | |||
