Twierdzenie o hierarchii dla współczynników aproksymacyjnych?

Jak dobrze wiadomo, problemy optymalizacji trudne dla NP mogą mieć wiele różnych współczynników aproksymacji, począwszy od posiadania PTAS, aż do braku przybliżenia w ramach dowolnego czynnika. Pomiędzy nimi mamy różne stałe, , itp.p o l y ( n $O(\log n)$$poly(n)$

Co wiadomo na temat zestawu możliwych proporcji? Czy możemy udowodnić jakąkolwiek „hierarchię aproksymacji”? Formalnie, na jakie funkcje i może się okazać, że istnieje problem z współczynnik przybliżenie ?g ( n ) f ( n ) ≤ α < g ( n $f(n)$$g(n)$$f(n)\leq \alpha < g(n)$

W przypadku, gdy , czy istnieje problem ze współczynnikiem przybliżenia dokładnie ?$\alpha=O(1)$$\alpha$

Istnieje hierarchia aproksymacji, główne znane przykłady: FPTAS EPTAS ⊆ PTAS ⊆ APX . Ale dla niedopuszczalności istnieje również NPO-PB .$\subseteq$ $\subseteq$ $\subseteq$

Istnieje wiele wyników na temat zestawu możliwych wskaźników, począwszy od wyników takich jak ten:

EPTAS ∖ FPTAS, chyba że P = N P ,$P||C_{max} \in$$\backslash$$P=NP$

do definiowania trudnych problemów APX / NPO-PB.

Niektóre referencje:

• NA PTAS: M. Cesati i L. Trevisan. O efektywności wielomianowych schematów aproksymacji czasu, 1997.
• Na NPOPB: V. Kann. Silne dolne granice zbliżalności niektórych problemów maksymalizacji pełnej NPO PB

Ale sugeruję, że najlepiej będzie sprawdzić Zoo w Złożoności, ponieważ zawiera wiele innych informacji i odniesień do tych przykładów, nawet Wikipedii

Ponadto, jak stwierdzono w komentarzach , wykazano ścisłe powiązanie, gdy , wykazano dla wielu problemów, takich jak pakowanie pojemników, planowanie maszyn (patrz iris.gmu.edu/~khoffman/papers/set_covering.html).$\alpha=O(1)$

Nadal uważam, że komentarz Suresha pod pytaniem wystarczy, aby pokazać, że możliwy jest każdy stosunek. Jeśli nie jesteś do tego przekonany, możesz na przykład spojrzeć na Boolean Constraint Satisfaction Problems (CSP).

Tło: Niech będzie predykatem arity k . Wystąpienie Max-CSP (P) jest ponad n ≫ k Zmienne logiczne x 1 , … , x n . Dosłowność to dowolna zmienna lub jej negacja. Instancja składa się z m ograniczeń, z których każda ma postać P ( λ 1 , … , λ k ), gdzie λ $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$są pewne literały, a celem jest znalezienie przypisania zmiennych, które maksymalizują ułamek spełniających ograniczeń. Na przykład w mamy P ( x 1 , x 2 , x 3 ) = x 1 ∨ x 2 ∨ x 3 . Zdefiniować p ( P ) jako frakcję 2 K możliwe wejścia, które spełniają P (dla 3 S A , T jest równe 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$). Trywialne jest przybliżenie dowolnego Max-CSP (P) współczynnikiem poprzez przypisanie losowych wartości do zmiennych (a następnie derandimację przy użyciu metody warunkowych oczekiwań). Zauważ, że mamy tutaj konwencję, że współczynniki aproksymacji są dodatnimi rzeczywistymi wartościami nie więcej niż 1. Predykat P jest odporny na aproksymację (AR), jeśli NP-trudno jest rozwiązać Max-CSP (P) lepiej niż przez współczynnik ρ ( P ) (tj. ρ ( P ) + ϵ dla dowolnego ustalonego ϵ > 0 ).$\rho(P)$$P$$\rho(P)$$\rho(P)+\epsilon$$\epsilon > 0$

Należy zauważyć, że każdy predykat AR wykazuje wąski próg aproksymacji . Wiadomym jest, że istnieją predykaty P z dowolnie małe p ( P ) , które są odporne na przybliżenie i tak pozostanie, nawet jeśli dodać do przyjmowania wejść P . Na przykład następujący artykuł pokazuje jeden taki wynik:$\rho(P)$$P$$\rho(P)$$P$

Per Austrin i Johan Håstad, Randomly Supported Independence and Resistance, SIAM Journal on Computing, vol. 40, nr 1, s. 1–27, 2011.

To dotyczy wszystkich racjonalnych progów, których mianownikiem jest potęga dwóch. W przypadku innych progów należy zauważyć, że jeśli wystarczy, aby wykazać, że dla każdego istnieje α ′ ≤ α, dla którego istnieje predykat AR z ρ ( P ) = α ′ (ponieważ zawsze można dodać zmienne obojętne i ograniczenia te, które są w trywialny sposób zadowalające, aby zwiększyć próg zbliżenia).$\alpha$$\alpha' \leq \alpha$$\rho(P) = \alpha'$