Hierarchiesatz für Approximationsverhältnisse?

Bekanntlich können NP-harte Optimierungsprobleme viele verschiedene Approximationsverhältnisse aufweisen, die von PTAS bis hin zur Unannäherbarkeit innerhalb eines Faktors reichen. Dazwischen haben wir verschiedene Konstanten, , usw.$O(\log n)$$poly(n)$

Was ist über die Menge der möglichen Verhältnisse bekannt? Können wir irgendeine Art von "Annäherungshierarchie" beweisen? Für welche Funktionen und können wir formal ein Problem mit dem Näherungsverhältnis ?$f(n)$$g(n)$$f(n)\leq \alpha < g(n)$

Gibt es für den Fall, dass , ein Problem mit dem Näherungsverhältnis genau ?$\alpha=O(1)$$\alpha$

Es ist eine Annäherung Hierarchie, die wichtigsten bekannten Beispiele: FPTAS EPTAS ⊆ PTAS ⊆ APX . Aber für die Unannäherbarkeit gibt es auch NPO-PB .$\subseteq$ $\subseteq$ $\subseteq$

Es gibt viele Ergebnisse über die Menge der möglichen Verhältnisse, die sich aus Ergebnissen wie diesem ergeben:

EPTAS ∖ FPTAS, es sei denn , P = N P ,$P||C_{max} \in$$\backslash$$P=NP$

APX / NPO-PB-harte Probleme zu definieren.

Einige Referenzen:

• ÜBER PTAS: M. Cesati und L. Trevisan. Zur Effizienz polynomialer Zeitnäherungsschemata, 1997.
• Auf NPOPB: V. Kann. Starke Untergrenzen für die Approximierbarkeit einiger NPO-PB-Complete-Maximierungsprobleme

Ich schlage jedoch vor, den Complexity Zoo zu überprüfen, da er über viele weitere Informationen und Referenzen zu diesen Beispielen verfügt, sogar über Wikipedia

Darüber hinaus wurde, wie in den Kommentaren angegeben, die enge Bindung bei für viele Probleme gezeigt, wie z.$\alpha=O(1)$

Ich denke immer noch, dass Sureshs Kommentar unter der Frage ausreicht, um zu zeigen, dass jedes Verhältnis möglich ist. Wenn Sie davon nicht überzeugt sind, können Sie sich zum Beispiel Boolean Constraint Satisfaction Problems (CSPs) ansehen.

Hintergrund: Sei ein Prädikat der Arität k . Eine Instanz von Max-CSP (P) liegt über n ≫ k Booleschen Variablen x 1 , … , x n . Ein Literal ist eine Variable oder deren Negation. Die Instanz besteht aus m Bedingungen, wobei jede die Form P ( λ 1 , … , λ k ) hat, in der λ $P: \{0,1\}^k \to \{0,1\}$$k$$n \gg k$$x_1, \ldots, x_n$$m$$P(\lambda_1, \ldots, \lambda_k)$$\lambda_i$sind einige Literale, und das Ziel ist es, eine Zuordnung der Variablen zu finden, die den Bruchteil der erfüllten Bedingungen maximiert. Zum Beispiel haben wir in P ( x 1 , x 2 , x 3 ) = x 1 ≤ x 2 ≤ x 3 . Definieren ρ ( P ) als der Anteil von 2 k möglichen Eingänge , die genügen P (für 3 S A T ist gleich 7 /$3SAT$$P(x_1, x_2, x_3) = x_1 \lor x_2 \lor x_3$$\rho(P)$$2^k$$P$$3SAT$$7/8$). Es ist trivial, jeden Max-CSP (P) durch Zuweisen von Zufallswerten zu Variablen mit einem Faktor zu approximieren (und dann unter Verwendung der Methode der bedingten Erwartungen zu derandimieren). Beachten Sie, dass wir hier die Konvention haben, dass Approximationsverhältnisse positive Reelle sind, die nicht größer als 1 sind. Ein Prädikat P ist approximationsresistent (AR), wenn es NP-schwer ist, Max-CSP (P) besser zu lösen als mit einem Faktor ρ ( P ). (dh ρ ( P ) + ε für jeden festen ε > 0 ).$\rho(P)$$P$$\rho(P)$$\rho(P)+\epsilon$$\epsilon > 0$

Man beachte, dass jedes AR-Prädikat eine enge Approximationsschwelle . Es ist bekannt, dass es Prädikate P mit willkürlich kleinem ρ ( P ) gibt , die approximationsresistent sind und dies auch dann bleiben, wenn Sie zu den akzeptierenden Eingaben von P hinzufügen . Das folgende Papier zeigt beispielsweise ein solches Ergebnis:$\rho(P)$$P$$\rho(P)$$P$

Per Austrin und Johan Håstad, Nach dem Zufallsprinzip unterstützte Unabhängigkeit und Widerstand, SIAM Journal on Computing, vol. 40, nein. 1, S. 1-27, 2011.

Damit werden alle rationalen Schwellenwerte berücksichtigt, deren Nenner eine Zweierpotenz ist. Beachten Sie für andere Schwellen, dass es für jedes ein α ′ ≤ α gibt, für das es ein AR-Prädikat mit ρ ( P ) = α ′ gibt (da es immer möglich ist, Dummy-Variablen und Nebenbedingungen von hinzuzufügen) trivial erfüllbar sind, um die Annäherungsschwelle zu erhöhen).$\alpha$$\alpha' \leq \alpha$$\rho(P) = \alpha'$