Algoritmos de aproximação de tempo super polinomial para problemas de otimização

8

Isso é motivado pela minha pergunta anterior, Algoritmos de aproximação de tempo super polinomial para MAX-3SAT . Para muitos problemas de otimização, para cada um deles temos um limite inferior de aproximação assumindo uma conjectura teórica de complexidade amplamente aceita. Em outras palavras, não há algoritmo de tempo polinomial para esses problemas de otimização com taxa de aproximação melhor que some (proporção diferente para cada problema).ααα

Existem problemas de otimização para os quais podemos alcançar uma taxa de aproximação melhor que se permitirmos algoritmos de tempo super-polinomial? Podemos obter melhores taxas de aproximação usando algoritmos de tempo quase-polinomiais ( ) ou mesmo usando algoritmos de tempo subexponenciais ( )?αnO(registron)2o(n)

Eu apreciaria uma pesquisa de tais resultados.

Mohammad Al-Turkistany
fonte

Respostas:

17

Um exemplo é o Conjunto Independente Máximo . É NP-difícil aproximar o problema com a razão (Zuckerman, 2007) . No entanto, Bourgeois et al. (2011) dá um simples n 1 / 2 -approximation algoritmo com o funcionamento de tempo S * ( 2 n1-ϵ n1/2. Aqui,nindica o número de vértices do gráfico de entrada e oó*notação Q couros factores polinomiais.O(2nregistron)nO

Outro exemplo é o problema da largura de banda . Dunagan e Vempala (2001) projetam um algoritmo com razão de aproximação e tempo de execução O ( n log n ) . Para meu conhecimento, o mais conhecido aproximação de tempo polinomial tem aproximação relação de O ( log 3 n ( log log n ) 1 / 4 ) (Lee, 2009) ; no entanto, não ω ( O(registro3n)O(nregistron)O(registro3n(registroregistron)1/4) limite inferior é conhecido pela melhor taxa de aproximação possível em tempo polinomial.ω(registron/registroregistron)

Serge Gaspers
fonte
Na verdade, para a largura de banda, parece haver um limite de superprobabilidade super-constante, especialmente se alguém estiver disposto a assumir que o NP não pode ser resolvido em tempo quase polinomial. O limite, fornecido em "Resultados da dureza para aproximar a largura de banda" por Dubey, Feige, Unger (JCSS 2011), é . cregistron/registroregistron
Michael Lampis