Beziehung zwischen festem Parameter und Approximationsalgorithmus

Fixed Parameter und Approximation sind völlig unterschiedliche Ansätze zur Lösung schwieriger Probleme. Sie haben unterschiedliche Motivation. Die Approximation sucht ein schnelleres Ergebnis mit einer ungefähren Lösung. Ein fester Parameter sucht nach einer exakten Lösung mit Zeitkomplexität in Bezug auf die Exponential- oder eine Funktion von k und die Polynomfunktion von n, wobei n die Eingabegröße und k der Parameter ist. Beispiel . $2^kn^3$

Nun meine Frage, gibt es eine obere oder gebundene Ergebnis senken basierend auf der Beziehung zwischen den festen Parameter und Annäherung nähert oder sie völlig haben keine relationship.For Beispiel für ein Problem wird gesagt, dass hart für einige $P$ $W[i]$ $i>0$ hat nichts mit C-Approximationsalgorithmus oder PTAS zu tun. Bitte geben Sie einige Referenzen an

cc.complexity-theory reference-request approximation-algorithms fixed-parameter-tractable Prabu
quelle

Verwandte, möglicherweise duplizieren?: Cstheory.stackexchange.com/questions/4906/…

Suresh Venkat

@suresh venkat Bei dieser Frage geht es um den Unterschied, NP-vollständige und feste Parameter zu verstehen. Wenn wir nur in Bezug auf die NP-Härte sprechen, dann sind unabhängige Menge und Vertex-Abdeckung buchstäblich gleich, aber wenn wir in Bezug auf feste Parameter sprechen, haben sie einen großen Unterschied. Vertex Cover hat gute fpt, während Independent Set ist W [1] schwer

Prabu

aber hier suche ich eine beziehung zwischen approximation und festem parameter.

Prabu

Ich denke, es gibt keine wirkliche Beziehung zwischen ihnen, aber wenn wir feste Parameter verwenden, können wir eine gute Annäherung haben, zum Beispiel beim Packen von Behältern (Makespan Scheduling), können Sie diese Beziehung sehen, oder zum Beispiel in beschränkten Treewidth-Diagrammen haben wir Annäherungen an einige Probleme .

Saeed

Antworten:

Es gibt verschiedene Zusammenhänge zwischen parametrisierter Komplexität und Approximationsalgorithmen.

Betrachten Sie zunächst die sogenannte Standardparametrierung eines Problems. Hier ist der Parameter, den Sie in der Optimierungsversion des Problems optimieren würden (Größe der Scheitelpunktabdeckung für das Scheitelpunktabdeckungsproblem, Breite der Baumzerlegung für das Treewidth-Problem usw.). Betrachten wir konkret Vertex Cover. Jeder Kernel mit einer linearen Anzahl von Scheitelpunkten für Vertex Cover impliziert einen konstanten Algorithmus für die Polynomzeitnäherung: Fügen Sie in die Näherungslösung alle Scheitelpunkte ein, die durch den Kernelisierungsalgorithmus in die Lösung gezwungen wurden, und alle Scheitelpunkte der kernelisierten Instanz . Andererseits implizieren Untergrenzen für den Approximationsfaktor Untergrenzen für die Größe eines Kernels. Zum Beispiel unter der Unique Games Conjecture, Khot und Regev (JCSS 2008)Ausschluss von Approximationsalgorithmen für Vertex Cover mit einem Verhältnis von , wodurch ein Kernel für Vertex Cover mit höchstens Vertices, $c<2$ $ck$ $c<2$ , ausgeschlossen wird.

EDIT: Die Argumentation für die Kernel-Untergrenze im vorigen Absatz ist sehr informell, und meines Wissens ist offen, ob solche Untergrenzen für die Kernelgröße auch für Vertex Cover bewiesen werden können. Wie @Falk in den Kommentaren betont, gilt das Argument für die meisten (alle?) Bekannten Kernel. Ich verstehe jedoch nicht, wie man die Existenz von Kernelisierungsalgorithmen ausschließen könnte, bei denen eine realisierbare Lösung der kernelisierten Instanz ein anderes Näherungsverhältnis aufweist als die entsprechende Lösung in der ursprünglichen Instanz.

Dann gibt es die Ausgabe von PTAS gegen FPTAS. Wenn wir eine Lösung innerhalb von vom Optimum finden wollen, können wir mit parametrieren . Dann entspricht ein PTAS einem XP-Algorithmus in der parametrisierten Einstellung, während ein FPTAS einem FPT-Algorithmus entspricht. Für eine untere Annäherungsgrenze können wir für kein Problem, dessen Standardparametrisierung W [1] -hart ist, ein EPTAS erwarten: Ausführen des EPTAS mit $(1+\epsilon)$ $1/\epsilon$ $\epsilon=1/(k+1)$ würde das Problem genau in der FPT-Zeit lösen.

Schließlich ist ein FPT-Approximationsalgorithmus ein Algorithmus mit einer FPT-Laufzeit und einem Approximationsverhältnis, das von dem Parameter abhängen kann. Beispielsweise hat die Standardparametrierung des Cliquewidth-Problems einen FPT-Approximationsalgorithmus mit einem Approximationsverhältnis (Oum, WG 2005) , während die Standardparametrierung des Independent Dominating Set keinen FPT-Approximationsalgorithmus mit hat Leistungsverhältnis für eine berechenbare Funktion , außer FPT = W [2] (Downey et al., IWPEC 2006) . Siehe (Marx, The Computer Journal 2008) $(2^{3k+2}-1)/k$ $g(k)$ $g$ für eine Umfrage zur FPT-Annäherung.

Serge Gaspers
quelle

@Gasper Sehen Sie bitte die Frage "Finden eines maximalen azyklischen Unterturniers bei zwei azyklischen Unterturnieren". Ich habe immer noch Zweifel mit meiner Antwort. Da Sie mit verwandten Problemen gearbeitet haben, können Sie mir helfen

Prabu

Ist der erste Absatz von Serge's Antwort richtig? Ergibt die Untergrenze für die Approximierbarkeit eine Untergrenze für die Größe des Kernels? Die ähnliche Aussage steht in Niedermeiers Buch, aber ist diese Aussage richtig?

XXYYXX

@XXYYXX: In seiner Antwort schrieb Serge: "Jeder Kernel mit einer linearen Anzahl von Vertices für Vertex Cover impliziert einen Algorithmus für die Polynom-Zeit-Approximation mit konstantem Faktor" mit einem kurzen Beweis. Genauer gesagt zeigt sein Argument, dass es einen Faktor-C-Approximationsalgorithmus gibt, wenn es einen Kernel mit ck-Eckpunkten für eine Konstante c gibt. Das Gegenteil ist: Wenn kein Faktor-C-Approximationsalgorithmus existiert, existiert kein Kernel mit ck-Eckpunkten.

Yoshio Okamoto

@Prabu: Ich habe Ihre Antwort auf die andere Frage kommentiert. @Yoshio: Danke, dass du die Frage von @ XXYYXX beantwortet hast.

Serge Gaspers

Tatsächlich gilt das Argument für wahrscheinlich alle bekannten Kernelisierungen. Ich sehe jedoch keinen Grund, warum es keinen geben sollte, der z. B. zuerst auf ein anderes Problem reduziert, dort kernelisiert und dann wieder auf Vertex Cover reduziert wird, sodass die resultierende Instanz keine Vertex-Korrespondenz mit der ursprünglichen Instanz aufweist. Das einzige, was wir wirklich zeigen können, scheint mir zu sein, dass Kernel, die Untergraphen sind, wahrscheinlich nicht kleiner als 2k sein werden.

Falk Hüffner

$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$

Weitere Charakterisierungen für zwei Approximationsklassen werden in [2, Theorem 6.5] vorgeschlagen.

Ein Problem ist

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

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

$(f)ptas^{\infty}$ $(XP)PFPT^w$ $\frac{1}{\epsilon}$

Polynomial Time Approximation Schemata und parametrisierte Komplexität . J. Chen et al. / Discrete Applied Mathematics 155 (2007) 180 - 193.
Struktur der Polynom-Zeit-Approximation . EJ van Leeuwen et al. Technischer Bericht UU-CS-2009-034, Dezember 2009.

Oleksandr Bondarenko
quelle