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

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

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

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

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

complexity-theory reference-request approximation parameterized-complexity templatetypedef
источник

Это теорема Cai и Чен (JCSS97), заявив , что « если задача оптимизации NP имеет схему аппроксимации полностью полиномиальное время, то фиксируется параметрическим сговорчивым. » Смотрите статью на Fixed-Parameter сговорчивость и аппроксимируемость Н.П. Оптимизация Проблемы .

Пол GD

И, конечно, в качестве следствия вы получите « Задачи оптимизации NP, которые являются -твердыми при равномерном сокращении, не имеют полностью приближенной схемы полиномиального времени, если только $W[1]$ $W[1] = FPT$ ».

Пол GD

@ PålGD- Хотя это , кажется , что выбор параметризации несколько произвольно; они выбирают параметр как значение оптимального решения для ввода задачи. Я полагаю , что технически работает, хотя это интеллектуально не очень выполнения.

templatetypedef

Люк Мэтисон дал очень хороший ответ ниже, и я думаю , что достаточно ответить на ваш вопрос.

Pål GD

Ответы:

На самом деле есть более сильный результат; Проблема заключается в классе , если он имеет fptas ¹ : -аппроксимация работает во времени , ограниченного $\mathrm{FPTAS}$ $\varepsilon$ (т.е. многочлен как по размеру, так и по коэффициенту аппроксимации). Существует более общий класскоторый ослабляет время, связанное с $(n+\frac{1}{\varepsilon})^{\mathcal{O}(1)}$ $\mathrm{EPTAS}$ - по существу,-подобное время работы относительно фактора аппроксимации. $f(\frac{1}{\varepsilon})\cdot n^{\mathcal{O}(1)}$ $\mathrm{FPT}$

Ясно, что является подмножеством , и оказывается, что является подмножеством в следующем смысле: $\mathrm{FPTAS}$ $\mathrm{EPTAS}$ $\mathrm{EPTAS}$ $\mathrm{FPT}$

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

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

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

$A$ $\Pi$ $A'$ $\Pi$ $k$ $(x,k)$ $A$ $x$ $\varepsilon := \frac{1}{k+1}$ $1+\frac{1}{k+1}$ $y$ $\text{cost}(x,y)$ $y$ $r(x,y)$ $y$ $\text{opt}(x)$ $\text{cost}(x,y) = r(x,y)\cdot \text{opt}(x)$

$\text{cost}(x,y) \leq k$ $\text{opt}(x) \leq \text{cost}(x,y) \leq k$ $\text{cost}(x,y) > k$ $r(x,y) \leq 1+\frac{1}{k+1}$ $A$

opt (x) = \frac{cost (x, y)}{r (x, y)} \geq \frac{k + 1}{1 + \frac{1}{k + 1}} > k

$\text{opt}(x) = \frac{\text{cost}(x,y)}{r(x,y)} \geq \frac{k+1}{1+\frac{1}{k+1}} > k$

$A'$ $A$ $\Box$

$\mathrm{FPT}$ $\mathrm{EPTAS}$ $\mathrm{FPT}$

Примечания:

$\mathrm{FPTAS}$ $\mathrm{EPTAS}$ $\mathrm{PTAS}$ $\mathrm{NPO}$

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

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