Parâmetro fixo e aproximação são abordagens totalmente diferentes para resolver problemas difíceis. Eles têm motivação diferente. A aproximação procura resultados mais rápidos com a solução aproximada. O parâmetro fixo procura uma solução exata com complexidade de tempo em termos da função exponencial ou de alguma função da função polinomial de n em que n é o tamanho da entrada e k é o parâmetro. Exemplo .
Agora, minha pergunta: existe algum resultado de limite superior ou inferior com base no relacionamento entre parâmetro fixo e abordagens de aproximação ou eles totalmente não têm nenhum relacionamento. Por exemplo, para um problema, é considerado W [ i ] difícil para alguns i > 0 não tem nada a ver com o algoritmo de aproximação c ou PTAS. forneça algumas referências
fonte
Respostas:
Existem várias conexões entre complexidade parametrizada e algoritmos de aproximação.
Primeiro, considere a chamada parametrização padrão de um problema. Aqui, o parâmetro é o que você otimizaria na versão de otimização do problema (o tamanho da cobertura de vértice para o problema de cobertura de vértice, a largura da decomposição da árvore para o problema de largura de árvore etc.). Vamos analisar concretamente a Vertex Cover. Qualquer kernel com um número linear de vértices para o Vertex Cover implica um algoritmo de aproximação de fator polinomial de fator constante: na solução aproximada, coloque todos os vértices que foram forçados à solução pelo algoritmo de kernelization e todos os vértices da instância kernelizada . Por outro lado, limites mais baixos no fator de aproximação implicam limites mais baixos no tamanho de um núcleo. Por exemplo, sob a conjetura de jogos exclusivos, Khot e Regev (JCSS 2008)exclui os algoritmos de aproximação do Vertex Cover com uma proporção de qualquer , que exclui um kernel do Vertex Cover com no máximo c k vértices, c < 2 também.c < 2 c k c < 2
EDIT: A argumentação para o limite inferior do kernel no parágrafo anterior é muito informal e, pelo que sei, está aberto se esses limites inferiores no tamanho do kernel podem ser comprovados, mesmo para a Vertex Cover. Como o @Falk aponta nos comentários, o argumento vale para a maioria (todos?) Dos kernels conhecidos. No entanto, não vejo como alguém poderia excluir a existência de algoritmos de kernelização em que uma solução viável da instância kernelizada tem uma taxa de aproximação diferente da solução correspondente na instância inicial.
Depois, há a questão do PTAS versus FPTAS. Se quisermos encontrar uma solução dentro do ideal, podemos parametrizar por 1 / ϵ . Então, um PTAS corresponde a um algoritmo XP na configuração parametrizada, enquanto um FPTAS corresponde a um algoritmo FPT. Para um limite inferior de aproximação, não podemos esperar um EPTAS para qualquer problema cuja parametrização padrão seja W [1]: difícil: executar o EPTAS com ϵ = 1 / ( k + 1 ) resolveria o problema exatamente no tempo do FPT.( 1 + ϵ ) 1 / ϵ ϵ=1/(k+1)
Finalmente, um algoritmo de aproximação do FPT é um algoritmo com tempo de execução do FPT e uma taxa de aproximação que pode depender do parâmetro. Por exemplo, a parametrização padrão do problema Cliquewidth possui um algoritmo de aproximação FPT com razão de aproximação (Oum, WG 2005), enquanto a parametrização padrão do Conjunto Dominante Independente não possui algoritmo de aproximação FPT com taxa de desempenhog(k)para qualquer função computávelg, a menos que FPT = W [2](Downey et al., IWPEC 2006). Ver(Marx, The Computer Journal 2008)(23k+2−1)/k g(k) g para uma pesquisa sobre aproximação FPT.
fonte
Existe um teorema conhecido [1, Teorema 3.1], caracterizando a classe de aproximaçãoFPTAS PFPT
Outras caracterizações para duas classes de aproximação são propostas em [2, Teorema 6.5].
fonte