Teorema da hierarquia para razões de aproximação?

Como é sabido, os problemas de otimização de NP-hard podem ter muitas proporções de aproximação diferentes, variando de ter um PTAS a não ser aproximado em nenhum fator. No meio, que tem várias constantes, , , etc. $O(\log n)$ $poly(n)$

O que se sabe sobre o conjunto de relações possíveis? Podemos provar qualquer tipo de "hierarquia de aproximação"? Formalmente, para que funções e , podemos provar que existe um problema com relação aproximação ? $f(n)$ $g(n)$ $f(n)\leq \alpha < g(n)$

No caso em que , existe um problema com a razão de aproximação exatamente ? $\alpha=O(1)$ $\alpha$

cc.complexity-theory approximation-hardness Jeremy Hurwitz
fonte

Uma prova desse teorema provavelmente se assemelharia a sabedoria.weizmann.ac.il/~oded/p_testHT.html . Dado um problema com o limite de aproximação conhecido

, tornamos o problema "mais fácil" de alguma forma, presumivelmente usando alguma forma de preenchimento, para obter um problema com o limite de aproximação

α

$\alpha$

f (α)

$f(\alpha)$

22411 Jeremy Hurwitz

não são constantes.

O (\log n)

$O(\log n)$

p o l y (n)

$poly(n)$

Tyson Williams

@TysonWilliams: Eu acho que ele quis dizer que entre PTAS e nenhuma aproximação existem constantes, log e poli (n) etc

Suresh Venkat

Você não precisaria descartar transformações triviais em que uma aproximação

para minimizar f imediatamente é

α

$\alpha$

aproximação

para minimizar

\sqrt{α}

$\sqrt{\alpha}$

\sqrt{f}

$\sqrt{f}$

Suresh Venkat

Quanto à sua última pergunta sobre α = O (1), o limite apertado foi mostrado para muitos problemas, como empacotamento de lixeiras, programação de máquinas (iris.gmu.edu/~khoffman/papers/set_covering.html)

Gopi

Respostas:

Há uma hierarquia de aproximação, as principais exemplos conhecidos: FPTAS EPTAS PTAS APX . Mas por falta de aproximação, também existe o NPO-PB . $\subseteq$ $\subseteq$ $\subseteq$

Existem muitos resultados sobre o conjunto de proporções possíveis, provenientes de resultados como este:

EPTAS FPTAS, a menos que , $P||C_{max} \in$ $\backslash$ $P=NP$

para definir problemas difíceis de APX / NPO-PB.

Algumas referências:

SOBRE PTAS: M. Cesati e L. Trevisan. Sobre a eficiência de esquemas de aproximação de tempo polinomial, 1997.
Em NPOPB: V. Kann. Limites inferiores fortes na proximidade de alguns problemas de maximização de NPO PB-complete

Mas sugiro que o melhor seja verificar o Zoológico da Complexidade, pois ele tem muito mais informações e referências sobre esses exemplos, até a Wikipedia

$\alpha=O(1)$

Gopi
fonte

Ainda acho que o comentário de Suresh abaixo da pergunta é suficiente para mostrar que qualquer proporção é possível. Se você não está convencido disso, pode olhar para os Problemas de satisfação com restrições booleanas (CSPs), por exemplo.

$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$ $3SAT$ $P(x_1, x_2, x_3) = x_1 \lor x_2 \lor x_3$ $\rho(P)$ $2^k$ $P$ $3SAT$ $7/8$ $\rho(P)$ $P$ $\rho(P)$ $\rho(P)+\epsilon$ $\epsilon > 0$

$\rho(P)$ $P$ $\rho(P)$ $P$

Por Austrin e Johan Håstad, Independência e Resistência Aleatoriamente Suportadas, SIAM Journal on Computing, vol. 40, n. 1, pp. 1-27, 2011.

$\alpha$ $\alpha' \leq \alpha$ $\rho(P) = \alpha'$

MCH
fonte