Из того, что я прочитал в preliminary version of a chapter of the book “Lectures on Scheduling”
edited by R.H. M¨ohring, C.N. Potts, A.S. Schulz, G.J. Woeginger, L.A. Wolsey, to appear around 2011 A.D.
Это определение PTAS :
Схема аппроксимации полиномиального времени ( PTAS ) для задачи - это схема аппроксимации, сложность по времени которой является полиномиальной по размеру входных данных.
и определение FPTAS
Схема полиномиальной аппроксимации по времени ( FPTAS ) для задачи является схемой аппроксимации, сложность по времени которой полиномиальна по размеру входных данных, а также полиномиальна по 1 / .ϵ
Тогда писатель говорит:
Следовательно, для PTAS было бы приемлемо иметь временную сложность, пропорциональную гдеразмер входного файла, хотя эта временная сложность экспоненциально в . FPTAS не может иметь временную сложность, которая экспоненциально возрастает в но временная сложность, пропорциональная , вполне подойдет. Что касается аппроксимации в наихудшем случае, FPTAS является самым сильным результатом, который мы можем получить для NP-трудной задачи. | Я | 1 / ϵ 1 / ϵ | Я | 8 / ε 3
Затем он предложил следующий рисунок, чтобы проиллюстрировать отношения между классами задач:
Вот мои вопросы:
Из определения PTAS и определения FPTAS как автор приходит к выводу, что FPTAS не может иметь временную сложность, которая экспоненциально возрастает в ? и какая разница, если он может иметь такую временную сложность?
Временная сложность, такая как , приемлема для FPTAS, но не для PTAS , тогда почему FPTAS считается подмножеством PTAS ?
Что он имеет в виду: FPTAS - это самый сильный результат, который мы можем получить для NP-трудной задачи.
В совокупности я хотел бы знать, что именно означают эти понятия и каковы их отличительные свойства.
Заранее спасибо.
Ответы:
Позвольте мне ответить на ваши вопросы по порядку:
По определению, задача имеет FPTAS, если существует алгоритм, который в случаях длиныN дает 1 + ϵ -приближение и выполняется в полиноме по времени от N и 1 / ϵ , то есть O ( ( n / ϵ )С) для некоторая постоянная С≥ 0 . Работающий время 21 / ϵ не принадлежит O ( ( n / ϵ )С) для любого С .O ( ( n / ϵ )С) лучше , чем алгоритм, время работы только гарантированно O ( nСеD / ϵ) , так как зависимость от ε лучше для первого алгоритма. Кроме того, для любого Е мы можем найти E- аппроксимацию 1 + 1 / nЕ за полиномиальное время, используя первый алгоритм, но не используя второй (по крайней мере, с учетом данной гарантии).
Алгоритм, время выполнения которой
Проблема, в которой1 + ϵ -приближение может быть найдено во времени ( n + 1 / ϵ )3 , определенно лежит в PTAS, поскольку для каждого ε это O ( n3) (упражнение) и, следовательно, полином от N .
Авторы имели в виду, что поскольку задача NP-сложной оптимизации не может быть решена точно за полиномиальное время, лучшее, на что мы можем надеяться, это то, что она будетε приближенной за полиномиальное время и, кроме того, с хорошей зависимостью от ε , Среди общих классов сложности FPTAS дает самую сильную гарантию зависимости от ε . Но на практике мы иногда получаем еще лучшую гарантию: время выполнения полиномиально по N и по журнал( 1 / ϵ ) , Так что не совсем верно, что FPTAS - самый сильный результат; это только самый сильный возможный результат среди опций PTAS, FPTAS, P. Если бы мы создали новый класс LPTAS (соответствующий полиному времени от N и в журнал( 1 / ϵ ) ), то это было бы более сильной гарантией.
Учитывая NP-сложную задачу оптимизации, она не может быть решена точно за полиномиальное время; лучшее, на что можно надеяться, - это приблизиться к нему эффективно. Некоторые проблемы NP-трудно приблизить к некоторой константеС> 1 . Что касается других, то можно решить проблему произвольно хорошо за полиномиальное время, и эти проблемы имеют PTAS и поэтому относятся к классу PTAS. Это может быть , что 1 + ϵ -приближение занимает много времени , пропорциональное е1 / ϵ , и поэтому мы можем применить только это эффективны при постоянном ε . Если проблема имеет FPTAS (и, следовательно, принадлежит классу FPTAS), то мы знаем, что зависимость от ε только полином, и поэтому мы можем аппроксимировать эффективно в пределах 1 + 1 / nС для любого С .
источник
источник