Сокращение разрыва
 | Эта статья может быть слишком технической для понимания большинства читателей . ( декабрь 2014 г. ) |
В теории сложности вычислений сокращение разрыва — это сведение к определенному типу проблемы принятия решения, известной как проблема c-пробела . Такие сокращения дают информацию о сложности аппроксимации решения оптимизационных задач . Короче говоря, проблема разрыва относится к проблеме, в которой цель состоит в том, чтобы отличить случаи, когда лучшее решение находится выше одного порога, от случаев, когда лучшее решение ниже другого порога, так что между двумя порогами есть разрыв. Уменьшение зазора можно использовать для демонстрации результатов неаппроксимируемости, поскольку, если проблему можно аппроксимировать до лучшего коэффициента, чем размер зазора, тогда алгоритм аппроксимации можно использовать для решения соответствующей проблемы зазора.
c - проблема с пробелом
[ редактировать ]Мы определяем проблему c -разрыва следующим образом: [ 1 ] учитывая задачу оптимизации (максимизации или минимизации) P , эквивалентная проблема c -пробела различает два случая: для входного k и экземпляра x проблемы P :
- . Здесь лучшее решение экземпляра x проблемы P имеет стоимость или оценку ниже k .
- . Здесь лучшее решение экземпляра x проблемы P имеет стоимость выше c ⋅ k . Таким образом, разрыв между двумя пороговыми значениями составляет c .
Обратите внимание, что всякий раз, когда OPT попадает между пороговыми значениями, нет никаких требований относительно того, каким должен быть выходной сигнал. проблемы Действительный алгоритм решения c -разрыва может ответить на что угодно, если OPT находится в середине разрыва. Значение c не обязательно должно быть постоянным; это может зависеть от размера экземпляра P . Обратите внимание, что c -аппроксимация решения экземпляра P по крайней мере так же сложна, как решение с c -промежутком версии P .
Аналогично можно определить проблему ( a , b ) -разрыва . Разница в том, что пороговые значения не зависят от входных данных; вместо этого нижний порог — a , а верхний порог — b .
Сокращение разрыва
[ редактировать ]Сокращение, вызывающее разрыв, — это сведение от задачи оптимизации к проблеме c-зазора, так что быстрое решение проблемы c-зазора позволит быстро решить задачу оптимизации. Термин «создание разрыва» возникает из-за природы сокращения: оптимальное решение в задаче оптимизации отображается на противоположной стороне разрыва от любого другого решения посредством сокращения. Таким образом, между оптимальным решением и любым другим решением образуется разрыв.
Простым примером сокращения, вызывающего пробелы, является неметрическая задача коммивояжера (т. е. когда стоимость ребер графа не обязательно удовлетворяет условиям метрики ) . Мы можем свести проблему гамильтонова пути на заданном графе G = (V, E) к этой задаче следующим образом: построить полный граф G' = (V, E') для задачи коммивояжера. Для каждого ребра e ∈ G' мы полагаем, что стоимость его прохождения равна 1, если e находится в исходном графе G, и ∞ в противном случае. Гамильтонов путь в исходном графе G существует тогда и только тогда, когда существует решение коммивояжера с весом (|V|-1). Однако если такого гамильтонова пути не существует, то лучший тур коммивояжера должен иметь вес не менее |V|. Таким образом, гамильтонов путь сводится к |V|/(|V|-1)-промежуточному неметрическому коммивояжёру.
Сокращение разрыва
[ редактировать ]Сокращение, сохраняющее разрыв, — это сокращение от проблемы c-зазора до проблемы c'-зазора. Точнее, нам дан экземпляр x проблемы A с |x| = n и хотите свести его к экземпляру x' проблемы B с |x'| = н'. Сведение с сохранением пробела от A к B — это набор функций (k(n), k'(n'), c(n), c'(n')) такой, что
Для задач минимизации:
- ОПТ A (x) ≤ k ⇒ ОПТ B (x') ≤ k', и
- ОПТ А (x) ≥ c⋅k ⇒ ОПТ B (x') ≥ c'⋅k'
Для задач максимизации:
- ОПТ A (x) ≥ k ⇒ ОПТ B (x') ≥ k', и
- ОПТ А (x) ≤ k/c ⇒ ОПТ B (x’) ≤ k’/c’
Если c' > c, то это редукция , усиливающая разрыв .
Примеры
[ редактировать ]Макс E3SAT
[ редактировать ]Эта проблема является формой булевой проблемы выполнимости (SAT), где каждое предложение содержит три различных литерала, и мы хотим максимизировать количество удовлетворенных предложений. [ 2 ]
Хостад показал, что (1/2+ε, 1-ε)-щельная версия аналогичной задачи MAX E3-X(N)OR-SAT является NP-трудной. [ 3 ] Задача MAX E3-X(N)OR-SAT — это разновидность SAT, где каждое предложение представляет собой операцию XOR трех различных литералов, ровно один из которых отрицается. Мы можем уменьшить MAX E3-X(N)OR-SAT до MAX E3SAT следующим образом:
- Предложение x i ⊕ x j ⊕ x k = 1 преобразуется в (x i ∨ x j ∨ x k ) ∧ (¬x i ∨ ¬x j ∨ x k ) ∧ (¬x i ∨ x j ∨ ¬x k) ) ∧ (x i ∨ ¬x j ∨ ¬x k )
- Предложение x i ⊕ x j ⊕ x k = 0 преобразуется в (¬x i ∨ ¬x j ∨ ¬x k ) ∧ (¬x i ∨ x j ∨ x k ) ∧ (x i ∨ ¬x j ∨ x k ) ∧ (x i ∨ x j ∨ ¬x k )
Если какое-либо условие не выполняется в исходном экземпляре MAX E3-X(N)OR-SAT, то в нашем экземпляре MAX E3SAT могут быть удовлетворены не более трех из четырех соответствующих пунктов. Используя аргумент пробела, следует, что экземпляр проблемы ДА имеет по крайней мере (1-ε) долю удовлетворенных условий, в то время как экземпляр проблемы НЕТ имеет не более (1/2+ε)(1) + (1/2-ε)(3/4) = (7/8 + ε/4)-доля выполненных условий. Отсюда следует, что (7/8 + ε, 1 - ε)-щель MAX E3SAT NP-трудна. Обратите внимание, что эта граница является жесткой, поскольку случайное назначение переменных дает ожидаемую долю удовлетворенных предложений 7/8.
Крышка этикетки
[ редактировать ]Проблема покрытия метками определяется следующим образом: задан двудольный граф G = (A∪B, E) с
- А знак равно А 1 ∪ А 2 ∪ ... ∪ А k , |A| = n и |A i | = н/к
- B знак равно B 1 ∪ B 2 ∪ ... ∪ B k , |B| = n и |B i | = н/к
Мы определяем «суперребро» между A i и B j , если существует хотя бы одно ребро из A i в B j в G, и определяем суперребро, которое будет покрыто, если хотя бы одно ребро из A i в B j покрыто .
В максимальным повторением версии задачи с нам разрешено выбирать по одной вершине из каждого A i и каждого B i , и мы стремимся максимизировать количество покрытых суперребер. В версии с минимальным повторением нам необходимо охватить каждое суперребро в графе и минимизировать количество выбираемых вершин. Мануранси и Мошковитц показывают, что (O(n 1/4 ), 1)-щельная версия обеих задач разрешима за полиномиальное время. [ 4 ]
См. также
[ редактировать ]Ссылки
[ редактировать ]- ^ Демейн, Эрик (осень 2014 г.). 6.890 /fall14/scribe/lec12.pdf «Алгоритмические нижние границы: забава с доказательствами твердости, лекция 12, примечания» (PDF) .
{{cite web}}: Проверять|url=ценность ( помощь ) - ^ Демейн, Эрик (осень 2014 г.). «Алгоритмические нижние границы: забава с доказательствами твердости, лекция 12» (PDF) .
- ^ Йохан, Хастад (июль 2001 г.). «Некоторые оптимальные результаты неаппроксимируемости» . Дж. АКМ . 48 (4). АКМ: 798–859. дои : 10.1145/502090.502098 . S2CID 5120748 .
- ^ Мануранси, Пасин; Мошковитц, Дана (2013). «Улучшенные алгоритмы аппроксимации для проекционных игр». Эса 2013 . 8125 (2). ЕКА: 683–694. arXiv : 1408.4048 . дои : 10.1007/s00453-015-0088-5 . S2CID 12959740 .