Связь между фиксированным параметром и алгоритмом аппроксимации

Фиксированный параметр и аппроксимация - это совершенно разные подходы для решения сложных задач. У них разная мотивация. Приближение ищет более быстрый результат с приближенным решением. Фиксированный параметр ищет точное решение с временной сложностью в терминах экспоненциальной или некоторой функции k и полиномиальной функции n, где n - размер ввода, а k - параметр. Пример . $2^kn^3$

Теперь мой вопрос, есть ли какой-либо результат верхней или нижней границы, основанный на связи между подходами с фиксированным параметром и приближением, или они полностью не имеют никакой связи. Например, для задачи говорят, что трудно для некоторых имеет ничего общего с алгоритмом c-приближения или PTAS. пожалуйста, предоставьте некоторые ссылки $P$ $W[i]$ $i>0$

cc.complexity-theory reference-request approximation-algorithms fixed-parameter-tractable Prabu
источник

Связанные, возможно, дубликаты?: Cstheory.stackexchange.com/questions/4906/…

Суреш Венкат

@suresh venkat Этот вопрос касается разницы в понимании NP-полного и фиксированного параметра. когда мы говорим только с точки зрения NP-твердости, то независимый набор и покрытие вершин буквально одинаковы, но когда мы говорим с точки зрения фиксированного параметра, они имеют огромную разницу. покрытие вершины имеет хороший fpt, тогда как независимый набор - это W [1] hard

Prabu

но здесь я ищу связь между приближением и фиксированным параметром.

Прабу

Я думаю, что между ними нет реальной связи, но, используя фиксированный параметр, мы можем получить хорошее приближение, например, в упаковке бина (планирование выполнения), вы можете увидеть это соотношение, или, например, в ограниченных графиках Treewidth у нас есть приближения по некоторым задачам. ,

Саид

Ответы:

Существует несколько связей между параметризованной сложностью и алгоритмами аппроксимации.

Сначала рассмотрим так называемую стандартную параметризацию задачи. Здесь параметр - это то, что вы оптимизируете в оптимизационной версии задачи (размер покрытия вершин для задачи покрытия вершин, ширина декомпозиции дерева для задачи Treewidth и т. Д.). Давайте конкретно посмотрим на Vertex Cover. Любое ядро с линейным числом вершин для покрытия вершин подразумевает алгоритм приближения с постоянным множителем за полиномиальное время: в приближенное решение помещают все вершины, которые были принудительно введены в решение алгоритмом ядра, и все вершины экземпляра с ядром. , С другой стороны, нижние оценки для коэффициента аппроксимации подразумевают более низкие оценки для размера ядра. Например, в предположении об уникальных играх, Хот и Регев (JCSS 2008)исключить алгоритмы аппроксимации для покрытия вершин с отношением любого , что исключает ядро для покрытия вершин с максимум вершинами, также. $c<2$ $ck$ $c<2$

РЕДАКТИРОВАТЬ: Аргументация для нижней границы ядра в предыдущем параграфе является очень неформальной, и, насколько мне известно, открыто, могут ли быть доказаны такие нижние границы для размера ядра, даже для Vertex Cover. Как указывает @Falk в комментариях, аргумент верен для большинства (всех?) Известных ядер. Тем не менее, я не вижу, как можно исключить существование алгоритмов ядра, где допустимое решение ядра с экземпляром имеет коэффициент аппроксимации, отличный от соответствующего решения в исходном случае.

Затем возникает проблема PTAS против FPTAS. Если мы хотим найти решение в пределах от оптимального, мы можем параметризовать как . Затем PTAS соответствует алгоритму XP в параметризованной настройке, тогда как FPTAS соответствует алгоритму FPT. Для приблизительной нижней границы мы не можем ожидать EPTAS для любой задачи, стандартная параметризация которой W [1] -hard: запуск EPTAS с решит проблему точно во время FPT. $(1+\epsilon)$ $1/\epsilon$ $\epsilon=1/(k+1)$

Наконец, алгоритм аппроксимации FPT - это алгоритм с временем выполнения FPT и коэффициентом аппроксимации, который может зависеть от параметра. Например, стандартная параметризация задачи Cliquewidth имеет алгоритм аппроксимации FPT с отношением аппроксимации (Oum, WG 2005) , тогда как стандартная параметризация Независимого доминирующего множества не имеет алгоритма аппроксимации FPT с коэффициент производительности для любой вычислимой функции , если только FPT = W [2] (Downey et al., IWPEC 2006) . См. (Маркс, The Computer Journal 2008) $(2^{3k+2}-1)/k$ $g(k)$ $g$ для обследования по приближению FPT.

Серж Гасперс
источник

@Gasper Можете ли вы увидеть вопрос "Поиск максимального ациклического суб-турнира с учетом двух ациклических суб-турниров". У меня все еще есть сомнения с моим ответом. Поскольку вы работали со связанной проблемой, вы можете мне помочь

Прабу

Первый абзац ответа Сергея правильный? Приводит ли нижняя граница аппроксимируемости к нижней границе размера ядра? Подобное утверждение есть в книге Нидермейера, но верно ли это утверждение?

XXYYXX

@XXYYXX: В ответе Сержа он написал «Любое ядро с линейным числом вершин для покрытия вершин подразумевает алгоритм приближения с постоянным множителем за полиномиальное время» с коротким доказательством. Точнее, его аргумент показывает, что если существует ядро с вершинами ck для некоторой константы c, то существует алгоритм приближения фактор-c. Противоположным является то, что: если не существует алгоритма аппроксимации фактора c, то ядра с ck вершинами не существует.

Ёсио Окамото

@Prabu: я прокомментировал ваш ответ на другой вопрос. @Yoshio: Спасибо, что ответили на вопрос @ XXYYXX.

Серж Гасперс

Фактически для всех известных зародышеобразований этот аргумент верен. Тем не менее, я не вижу причин, почему не должно быть такого, который, например, сначала сводится к другой проблеме, ядрируется там, а затем возвращается к покрытию вершин, так что результирующий экземпляр не имеет соответствия вершин с исходным. Поэтому мне кажется, что единственное, что мы можем действительно показать, - это то, что ядра, которые являются подграфами, вероятно, будут не меньше 2k.

Фальк Хюффнер,

$FPTAS$ $PFPT$

$Q=(I_Q, S_Q, f_Q, opt_Q)$ $NP$ $Q$ $FPTAS$ $Q$ $PFPT$

$PFPT$

$NP$ $Q$ $PFPT$ $O(|x|^{O(1)}k^{O(1)})$ $|x|$ $x$

Другие характеристики для двух приближенных классов предложены в [2, теорема 6.5].

Проблема в

$PTAS$ $ptas^{\infty}$ $XP^w$

$FPTAS$ $fptas^{\infty}$ $PFPT^w$

$(f)ptas^{\infty}$ $(XP)PFPT^w$ $\frac{1}{\epsilon}$ and bounding from below an optimum value.

Polynomial time approximation schemes and parameterized complexity. J. Chen et al. / Discrete Applied Mathematics 155 (2007) 180 – 193.
Structure of Polynomial-Time Approximation. E. J. van Leeuwen et al. Technical Report UU-CS-2009-034, December 2009.

Oleksandr Bondarenko
источник