Х. Пападимитриу, К. Стайглиц - Комбинаторная оптимизация (1125252), страница 87
Текст из файла (страница 87)
Такое благоприятное положение дел, естественно, требует определения, Определение 17.3. Будем говорить, что алгоритм является полиномиальной приближенной схемой (ППС) для задачи оптимизации А, если по данным индивидуальной задаче А и е>0 он выдает еприближенное решение за время, ограниченное полиномом (зависящим от е) от длины индивидуальной задачи. () Следовательно, выше мы описали ППС для задачи ОПТИМИЗАЦИОННЫЙ 0-1-РЮКЗАК; полипом, зависящий от е, имеет вид р, (и) =(1(а) и'. Таким образом, оценка полиномиальна относительно и и 1(ее Это очень удачная ситуация, поскольку определение !7.3 допускает, например, полиномы вида р, (и) =п'(" или и" '. Чтобы понять разницу, вычислите во всех трех случаях р, ((и).
В задаче 4 приведены реальные примеры таких 439 17.8. 17риближениме схемы 1 ',ППС. Для различения этих двух типов схем добавим вторую ;часть к определению 17.3. Определение !7.3 (продолжение). ППС называется полностью полиномиальной приближенной схемой (ПППС), если время ее работы ограничено полиномом как от длины индивидуальной задачи, так и от 1,'е. (3 Можно следующим образом суммировать наши обсуждения. Теорема !7.8. Алгоритм ДП-1Ъ', приведенный на рис. 17.18, зто ПППС для задачи ОПТИМИЗАЦИОИИЫИ 0-1-РТОКЗАК 1.
Пусть см — наибольшее из чисел с . /' 2. Положить 1=- 1 (ои1з (зси/и! |. 3. Длн /=1, ..., л выполнить с:=! с г10! | !О'. 4. Применить ДП-!П к индивидуальной задаче (ш„..., ш„; ст, с„.„с„; ((), Рис. 17.18. Алгоритм ДП.!Ч. Попробуем теперь выделить те черты задачи ОПТИМИЗАЦИОННЪ|Й 0-1-РЮКЗАК, которые позволили нам преобразовать псевдополиномнальный алгоритм ДП-П| в ПППС ДП-1Ч.
Важным свойством этой задачи является то, что, как отмечено выше, в любой индивидуальной задаче параметры 5=(тсь..., шч, К), связанные с проверкой на допустимость, не пересекаются с параметрами ()= = (с„..., са ),используе нымн для вычисления стоимости. Ключевой момент — это то, что сложность алгоритма ДП-П| ограничена не только полиномом от 171 и пнгп(!), но и, в частности, полиномом от 11! и с, наиболыпего числа среди ср 1'.ще одним свойством регулярности, которое делает возможной теорему 17.8, является тот факт, что оптимальная стоимость с, и с„полиномнально связаны через 1|(; т.
е. для некоторых двух полиномов р, и р, имеют место неравенства Ст~(Рт(171, С ) И Сь~~Рт(/I!, Сг), Наконец, еще одна важная черта — это то, что стоимость произвольного фиксированного допустимого решения является линейным функционалом относительно коэффициентов с, Мы оставляем чита- гелю в качестве упражнения установить, что алгоритм ДП-1Ч явияется в действительности примером намного болееобщего метода построения ПППС по некоторому псевдополиномиальному алгоритиу.
Теорема 17.9. Пусть все индивидуальные задачи 7 =(5, О) для задачи оптимизации А таковы, что О=(аь..., д„) — зто множе:тпва целых чисел, и а) оптимальная стоимость с, для данной индивидуальной задачи удавлетпворяет при некоторых полинсмах р, и р, неравенствам с ~ Гл. 17. Приближенные алгоритма 440 (р, (11), д) и д<р,(!1~, с,), где д — наибольшее целое число, появляюи4ееся в Я; б) стоимость с(1, 6) для любого данного допустимого решения 1 является линейным функционалом от (дь..., д„); в) задачу А можно ре1иить с помои(ыо некоторого алгоритма, время работы которого ограничено величиной р, ( ~11, д), где р, — некоторый полинам. Тогда для А имеется ПППС.
Отметим, что условия а) и б), несмотря на их технический вид, справедливы для многих задач оптимизации. 4 7.4 Отрнцатепьные разупьтаты Для некоторых комбинаторных задач оптимизации теорию ЖР-полноты можно применять для доказательства не только того, что этн задачи невозможно точно решить полиномиальными алгоритмами (если Р ~ 1ч'Р), но также и того, что для них не существует в-приближенньГх алгоритмов для различных областей изменения е (опять, если Р Ф 1ч'Р). В этом параграфе мы докажем три показательных результата такого сорта.
Первая теорема касается общей ЗК. Теорема 17.10. Если Р ~ ЧР, то не суи4ествует е-приближенного полиномиального алгорит,иа для ЗК при любом е)0, Доказательство. Допустим, что существует е-приближенный полиномиальный алгоритм Ан для ЗК при некотором е)0. Докажем, что тогда имеется полипомиальный алгоритм Аым решающий задачу ГАМИ1!ЬТОНОВ ЦИКЛ. Так какэта задача А1Р-полна, то отсюда будет следовать наша теорема.
Алгоритм А„„работает следующим образом. По произвольному данному графу 6:=(У, Е) он строит индивидуальную ЗК с городами. Расстояние й; берется равным 1, если [1, 1) — ребро графа 6; в противном случае й;1=-2+в~У~. Затем А„„применяет к этой индивидуальной задаче предполагаемый алгоритм А,. Мы утверждаем, что алгоритм А„выдаст обход стоимогли ~У~ тогда и только тогда, когда в 6 имеется гамильтонов цикл; отсюда будет вытекать, что алгоритм А„„корректно решает задачу ГАМИЛЬТОНОВ ЦИКЛ за полиномиальное время. В одну сторону наше утверждение очевидно. Если А„выдает обход стоимости ~У~, это означает, что существует обход, использующий только расстояния 1, так как в этой инднвидуальнойЗК кратчайшее расстояние равно 1.
Таким образом, в 6 имеется гамильтонов цикл. Для доказательства обратного утверждения предположим, что А, выдает обход длины, большей, чем )У|, но в 6 существует все же гамильтонов цикл, Длина этого обхода должна быть не меньше, чем !7.4. Ошрннотельные резулыиаты 44! 1+ (!+г) ~[г[, поскольку следующее по длине расстояние посче !— это 2+з~)г[. С другой стороны, так как в 6 имеется гамильтонов цикл, то оптимальный обход имеет длину ![г~.
Поэтому обход, выданный алгоритмом е(„не является е-подоптимальным, так как )+()+е) ! р ! — ) !'! ! ! !'! 1!г! Пришли к противоречию. Напомним, что для ЗКНТ имеется 172-приближенный алгоритм (см. э 16.2), который умно использует неравенство треугольника. Теорема !7.!О показывает, что для общей задачи невозможны а- приближенные алгоритмы — даже при е=!000. Следующий результат касается максимизационного варианта задачи КЛИКА: в данном графе найти наибольший полный подграф. Для доказательства следующей теоремы нам потребуются вначале некоторые факты нз теории графов.
Определение 1!.4. Пусть 6=(1', Е) — некоторый граф. Граф ба=([га, Е') — это граф с множеством вершин [га=-[гм [г и множеством ребер Е'=([(о, и), (и', и')): либо а=о' и[и, и'[РЕ, либо [а, и')РЕ). Например, если б — граф, изображенный на рис. 17.19(а), то б' — это граф, приведенный на рис. 17.19(б) (связки ребер являются полными двудольными графами). Д Следующая лемма устанавливает связь между этой конструкцией и задачей о клике. Лемма 17.3.
В б имеется клика размера я тогда и толька тогда когда в 6' имеется клика размера 'нз. доказательство. Пусть в 6 имеется клика С= — (п„пм..., пз). Тогда в 6', очевидно, имеется клика С'=((и, и): и, ирС) размера Гга. Для доказательства в обратную сторону предположим, что вб' имеется клика С' размера яа, но в б нет клики размера й. Множество 0=(п: ЭиЕ)г, такое, что (о, и)рС'), очевидно, является кликой в г 6; поэтому [0[(Ф вЂ” 1.
Следовательно, одно из [0~ множеств Р,= =(и: (а, и)сЕ) для пЕ0 должно содержать я или более вершйн. Нетрудно видеть, что такое множество также является кликой; этим лемма доказана. [) Теорема 17.1!. Если для задачи о клике имеется палинамиальнь!й е-приближенный алгоритм для некоторого 1)е ) О, то для нее имеется палиномиальный и-приближенный алгоритм для всех 1)з 0 '), ') Так как задача о клике нвлнетсн задачей максимизании, то имеет смысл рассматривать только относительные ошибки е, меньшие !. Гл.
17. Приближенные илгоритии Доказательство. Пусть для задачи о клике для некоторого е ) О имеется полиномиальный е-приближенный алгоритм и7а, Построим вначале, используя и7„полиномиальный 6-приближенный алгоритм и7е, где б ( е. Алгоритм и7а работает следующим 'з 1а) ( 4 ел) з) 1вз~ "з (б) Рис.
17л9. образом. По данному графу 6 он строит 6* и затем применяет к нему алгоритм и7е По клике С' графа ба он выбирает наибольшее из множеств 1:) и Р, для о~О, как в доказательстве леммы. Полученное в результате множество С является кликой графа б и удовлетворяет неравенству ( С ~ ))Рг(СЯ. 443 17.4. Отрицательные результата Пусть теперь й — размер наибольшей клики в 6; тогда по лемме наибольшая клика в (Уе содержит й' вершин Так как алгоритм А, является е-приближенным, то Уеь — (Оь( ~(е или (С'!)Уг'(1 — е). Отсюда и поэтому алгоритм А„ является б-приближенным, где 6 = = 1 — )Г! — е, Если этот процесс повторяется рекуррентно г раз, получаем 6-приближенный алгоритм для 6=1 — (1 — е)а" Выбирая г настолько большим, чтобы выполнялось неравенство 2 (оя (( — ь) 1оя (1 — б) ' получаем требуемый полиномиальный 6-приближенный алгоритм.
Таким образом, для задачи о клике существуют две крайние воз. можности: либо для нее нет е-приближенного алгоритма, аналогично общей ЗК, либо для нее имеется ППС. Может ли для нее быть ПППС? Следующии результаз показывает, что не может. Теорема 17.12. Пусть задача оптимизации А обладает следующими свойствами.
а) Вариант распознавания для А является сильно НР-полнеем, б) Для любой индивидупльной задачи У задачи А оптимальная етоимость удовлетворяет неравенству с, = р(пип(У)) для некотогюго полинома р(п). Тогда если Р Ф Уч Р, то длч А не существует ПППС. Доказательсепво, Предположим, что для Л существует ПППС. Тогда мы построим псевдополиномиальный алгоритм Ачэ котоэый решает А. Так как вариаш распознавания для А является ильпо УчР-полным, этим (согласно теореме 16.4) доказательство 5удет завершено.
Алгоритм Ат для данной индивидуальной задачи У ьадачи А просто вызывает ПППС для А с относительной ошибкой е-= =1У(р(пшп(У))+1). Так как оптимальная стоимость ограничена зеличиной р(ппт(У)), то только точное решение задачи У может быть е-приближенным, и, следовательно, алгоритм Ае точно репает задачу Л. Чтобы показать, что А е — псевдополиномиальный алгоритм, напомним, что время работы ПППС не превосходит д(!У1, 1(е) для некоторого полинома д.
Поэтому время работы алгоритма Ат ограничено величиной у(!У1, р(ппгп(У))+1), которая является толиномом от (У! и пшп(У). (] Гл. 17. Приближенные ллаоришмы Задачи !. В лемме 15.4 было доказано, что задачи ВЕРШИННОЕ ПОКРЫТИЕ, КЛИКА и НЕЗАВИСИМОЕ МНОЖЕСТВО эквивалентны. Л1ожете ли вы в связи с этим преобразова~ь алгоритм 2 из 6 17.1 в приближенные алгоритмы для задач КЛИКА и НЕЗАВИСИМОЕ МНОЖЕСТВО? Почему нет? (Примечание. Трудно разработать теорию приближенных алгоритмов, которая бы шла параллельно теории МР-полноты, Одной из причин этого является чувствительность стоимости даже к очень простым сведениям, примерам чему служит данная задача.) 2".
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
