Определение PTAS против FPTAS

13

Из того, что я прочитал в 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|я|1/ε|я|1/ε1/ε|я|8/ε3

Затем он предложил следующий рисунок, чтобы проиллюстрировать отношения между классами задач:

введите описание изображения здесь

Вот мои вопросы:

  1. Из определения PTAS и определения FPTAS как автор приходит к выводу, что FPTAS не может иметь временную сложность, которая экспоненциально возрастает в ? и какая разница, если он может иметь такую ​​временную сложность?1/ε

  2. Временная сложность, такая как , приемлема для FPTAS, но не для PTAS , тогда почему FPTAS считается подмножеством PTAS ?(N+1/ε)3

  3. Что он имеет в виду: FPTAS - это самый сильный результат, который мы можем получить для NP-трудной задачи.

  4. В совокупности я хотел бы знать, что именно означают эти понятия и каковы их отличительные свойства.

Заранее спасибо.

М ама Д
источник
Откуда вы взяли, что «временная сложность, подобная , приемлема для FPTAS, но не для PTAS »? (n+1/ϵ)3
1
Не размещайте более одного вопроса в одном сообщении, пожалуйста. Вполне возможно, что понимание ответа на ваш первый вопрос заставляет остальных следовать. (Имхо, ваша проблема в том, что вы не понимаете, что означает «и также многочлен от 1 / ϵ».)
Рафаэль
@RickyDemer по определению: его временная сложность является полиномиальной по размеру ввода (это означает )N
M ам D
... является многочленом п(N+1/ε)3N
@RickyDemer вы правы, я ошибся. Спасибо.
М А Д Д

Ответы:

15

Позвольте мне ответить на ваши вопросы по порядку:

  1. По определению, задача имеет FPTAS, если существует алгоритм, который в случаях длины N дает 1+ε -приближение и выполняется в полиноме по времени от N и 1/ε , то есть О((N/ε)С) для некоторая постоянная С0 . Работающий время 21/ε не принадлежит О((N/ε)С) для любого С .
    Алгоритм, время выполнения которой О((N/ε)С) лучше , чем алгоритм, время работы только гарантированно О(NСеD/ε) , так как зависимость от ε лучше для первого алгоритма. Кроме того, для любого Е мы можем найти E- аппроксимацию 1+1/NЕ за полиномиальное время, используя первый алгоритм, но не используя второй (по крайней мере, с учетом данной гарантии).

  2. Проблема, в которой 1+ε -приближение может быть найдено во времени (N+1/ε)3 , определенно лежит в PTAS, поскольку для каждого ε это О(N3) (упражнение) и, следовательно, полином от N .

  3. Авторы имели в виду, что поскольку задача NP-сложной оптимизации не может быть решена точно за полиномиальное время, лучшее, на что мы можем надеяться, это то, что она будет ε приближенной за полиномиальное время и, кроме того, с хорошей зависимостью от ε , Среди общих классов сложности FPTAS дает самую сильную гарантию зависимости от ε . Но на практике мы иногда получаем еще лучшую гарантию: время выполнения полиномиально по N и по журнал(1/ε), Так что не совсем верно, что FPTAS - самый сильный результат; это только самый сильный возможный результат среди опций PTAS, FPTAS, P. Если бы мы создали новый класс LPTAS (соответствующий полиному времени от N и в журнал(1/ε) ), то это было бы более сильной гарантией.

  4. Учитывая NP-сложную задачу оптимизации, она не может быть решена точно за полиномиальное время; лучшее, на что можно надеяться, - это приблизиться к нему эффективно. Некоторые проблемы NP-трудно приблизить к некоторой константе С>1 . Что касается других, то можно решить проблему произвольно хорошо за полиномиальное время, и эти проблемы имеют PTAS и поэтому относятся к классу PTAS. Это может быть , что 1+ε -приближение занимает много времени , пропорциональное е1/ε , и поэтому мы можем применить только это эффективны при постоянном ε . Если проблема имеет FPTAS (и, следовательно, принадлежит классу FPTAS), то мы знаем, что зависимость от εтолько полином, и поэтому мы можем аппроксимировать эффективно в пределах 1+1/NС для любого С .

Юваль Фильмус
источник
Пожалуйста, не поощряйте нежелательное поведение публикации.
Рафаэль
1

|я|знак равноNεN1/εNεε1/εNпоLY(N,1/ε)N4(1/ε)3+(1/ε)8N1/εN1/ε

Кириак Антоний
источник
2
εεεε1/ε