Почему все проблемы в FPTAS также в FPT?

11

Согласно статье в Википедии о схемах аппроксимации за полиномиальное время :

Все проблемы в FPTAS доступны для фиксированных параметров.

Этот результат меня удивляет - эти занятия, похоже, совершенно не похожи друг на друга. FPTAS характеризует проблемы по тому, насколько легко их аппроксимировать, а FPT характеризует проблемы по их сложности относительно какого-либо параметра. К сожалению, Википедия (на данный момент я задаю этот вопрос) не дает ссылки на это.

Есть ли стандартное доказательство этого результата? Или я могу обратиться к источнику, чтобы узнать больше об этой связи?

templatetypedef
источник
2
Это теорема Cai и Чен (JCSS97), заявив , что « если задача оптимизации NP имеет схему аппроксимации полностью полиномиальное время, то фиксируется параметрическим сговорчивым. » Смотрите статью на Fixed-Parameter сговорчивость и аппроксимируемость Н.П. Оптимизация Проблемы .
Пол GD
И, конечно, в качестве следствия вы получите « Задачи оптимизации NP, которые являются -твердыми при равномерном сокращении, не имеют полностью приближенной схемы полиномиального времени, если только W [ 1 ] = F P TW[1]W[1]=FPT ».
Пол GD
@ PålGD- Хотя это , кажется , что выбор параметризации несколько произвольно; они выбирают параметр как значение оптимального решения для ввода задачи. Я полагаю , что технически работает, хотя это интеллектуально не очень выполнения.
templatetypedef
Люк Мэтисон дал очень хороший ответ ниже, и я думаю , что достаточно ответить на ваш вопрос.
Pål GD

Ответы:

14

На самом деле есть более сильный результат; Проблема заключается в классе , если он имеет fptas 1 : ε -аппроксимация работает во времени , ограниченного ( п + 1FPTASε(т.е. многочлен как по размеру, так и по коэффициенту аппроксимации). Существует более общий классEPTAS,который ослабляет время, связанное сf(1(n+1ε)O(1)EPTAS- по существу,FPT-подобное время работы относительно фактора аппроксимации.f(1ε)nO(1)FPT

Ясно, что является подмножеством E P T A S , и оказывается, что E P T A S является подмножеством F P T в следующем смысле:FPTASEPTASEPTASFPT

Теорема. Если задача НКО имеетΠ eptas, то Π, параметризованная стоимостью решения, задается фиксированным параметром.Π

Теорема и доказательство даны в Flum & Grohe [1] как теорема 1.32 (стр. 23-24), и они приписывают ее Базгану [2], что ставит его за два года до более слабого результата Кая и Чена (но во французском технический отчет).

Я дам набросок доказательства, потому что я думаю, что это хорошее доказательство теоремы. Для простоты я сделаю версию минимизации, просто мысленно сделаю соответствующие инверсии для максимизации.

AΠAΠk(x,k)Axε:=1k+11+1k+1ycost(x,y)yr(x,y)yopt(x)cost(x,y)=r(x,y)opt(x)

cost(x,y)kopt(x)cost(x,y)kcost(x,y)>kr(x,y)1+1k+1A

opt(x)=cost(x,y)r(x,y)k+11+1k+1>k

AA

FPTEPTASFPT

Примечания:

  1. FPTASEPTASPTASNPO

[1]: Дж. Флум и М. Гроэ, « Параметризованная теория сложности» , Springer, 2006.
[2]: C. Bazgan. Schémas d'approximation et complexité paramétrée , Rapport de DEA, Université Paris Sud, 1995.

Люк Мэтисон
источник