Дополнительную расслабленность (CS) обычно учат, когда говорят о двойственности. Он устанавливает хорошее соотношение между основным и двойственным ограничением / переменными с математической точки зрения.
Две основные причины применения CS (как преподается в аспирантуре и учебниках):
- Для проверки оптимальности ЛП
- Чтобы помочь решить двойную
Учитывая сегодняшнюю вычислительную мощность и полиномиальные алгоритмы для решения LP, CS по-прежнему актуален с прагматической точки зрения? Мы всегда могли бы решить двойственные проблемы и рассмотреть оба пункта выше. Я согласен, что «более эффективно» решать дуал с помощью CS, но так ли это? Или в CS есть нечто большее, чем кажется на первый взгляд? Где именно CS полезен помимо двух вышеуказанных пунктов ? Я часто видел тексты, ссылающиеся на концепцию CS, когда речь идет об алгоритмах аппроксимации, но я не понимаю его роль там.
Ответы:
Дополнительное расслабление является ключевым моментом при разработке алгоритмов первичного двойственного типа. Основная идея:
Классическим примером является венгерский алгоритм. Алгоритм Форда-Фулкерсона можно рассматривать как еще один пример. Обратите внимание, что шаг 2. является проблемой выполнимости, которая часто проще, чем исходная проблема оптимизации, и также часто может быть решена комбинаторно. Это сила дополнительной расслабленности. Например, в случае двухстороннего сопоставления с минимальными затратами шаг 2 сводится к проверке, существует ли идеальное сопоставление, используя только острые края. В случае максимального потока - шаг 2 сводится к проверке, разделяют ли насыщенные ребра и .s t s t
Первично-двойственные алгоритмы хороши по многим причинам. С философской точки зрения, они дают больше понимания, чем общий алгоритм. Они обычно дают сильно полиномиальные алгоритмы времени, тогда как у нас все еще нет сильно полиномиальных LP-решателей. Они часто более практичны, чем универсальные алгоритмы. Это особенно верно, если мы не можем записать LP явно, и наш единственный другой выбор - алгоритм эллипсоида, который имеет место с недвойственным согласованием и алгоритмом Эдмондса.
Primal-dual также является очень полезной основой для алгоритмов аппроксимации, используя расслабленные версии дополнительной слабости. Это было полезно при разработке алгоритмов аппроксимации для NP-сложных задач (см., Например, главу 7 книги Уильямсона-Шмойса ) и при разработке онлайн-алгоритмов с хорошим конкурентным соотношением (см. Книгу Бухбиндера и Наора ). Дело в том, что алгоритм поддерживает решение двойственной релаксации LP сложной задачи и на каждом шаге либо находит целочисленное первичное выполнимое такое что приближенная комплементарная слабость удовлетворяется, либо улучшает двойное решениеy x y , Приближенная дополнительная слабость является условием следующего вида: если то соответствующее двойное ограничение является жестким, а если , то соответствующее первичное ограничение будет жестким, если масштабируется с помощью . Это дает коэффициент приближения . Все это очень хорошо объяснено в двух вышеупомянутых источниках.xi>0 yj>0 x α α
источник