Relação entre parâmetro fixo e algoritmo de aproximação

13

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 .2kn3

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ênciasPW[i]i>0

Prabu
fonte
1
Relacionado, possivelmente duplicado?: Cstheory.stackexchange.com/questions/4906/…
Suresh Venkat
1
@suresh venkat Essa pergunta é sobre a diferença no entendimento do parâmetro NP-completo e fixo. quando falamos apenas em termos de dureza NP, os conjuntos independentes e a cobertura de vértices são literalmente iguais, mas quando falamos em termos de parâmetros fixos, eles têm uma enorme diferença. tampa vértice tem boa FPT Considerando conjunto independente é W [1] duro
Prabu
mas aqui estou procurando uma relação entre aproximação e parâmetro fixo.
Prabu
Eu acho que não existe uma relação real entre eles, mas, usando o parâmetro fixo, podemos ter uma boa aproximação; por exemplo, no empacotamento de bin (programação de makepan), você pode ver essa relação ou, por exemplo, nos gráficos de largura de árvore limitada, temos aproximações em alguns problemas. .
Saeed

Respostas:

16

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<2ckc<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+21)/k g(k)g para uma pesquisa sobre aproximação FPT.

Serge Gaspers
fonte
@ Gasper Você pode ver a pergunta "Como encontrar um sub-torneio acíclico máximo com dois sub-torneios acíclicos". Eu ainda tenho dúvidas com a minha resposta. Como você trabalhou com problema relacionado, você pode me ajudar
Prabu
O primeiro parágrafo da resposta de Serge está correto? O limite inferior na aproximabilidade produz um limite inferior no tamanho do kernel? A afirmação semelhante está no livro de Niedermeier, mas esta afirmação está correta?
XXYYXX
1
@XXYYXX: Na resposta de Serge, ele escreveu "Qualquer núcleo com um número linear de vértices para o Vertex Cover implica um fator constante de algoritmo de aproximação de tempo polinomial" com uma prova curta. Mais precisamente, seu argumento mostra se existe um kernel com vértices ck para alguma constante c, então existe um algoritmo de aproximação fator-c. O contrapositivo é: se não existe um algoritmo de aproximação fator-c, então nenhum núcleo com vértices ck existe.
Yoshio Okamoto 21/03
@ Prabu: Comentei sua resposta para a outra pergunta. @ Yoshio: Obrigado por responder à pergunta de @ XXYYXX.
precisa
1
De fato, para provavelmente todas as kernelizações conhecidas, o argumento é válido. No entanto, não vejo razão para que não exista um que, por exemplo, se reduz primeiro a outro problema, faça o kernelize ali e depois volte ao Vertex Cover, para que a instância resultante não tenha correspondência de vértices com a inicial. Portanto, parece-me que a única coisa que realmente podemos mostrar é que os kernels que são subgráficos provavelmente não serão menores que 2k.
Falk Hüffner 28/03
7

Existe um teorema conhecido [1, Teorema 3.1], caracterizando a classe de aproximação FPTASPFPT

Q=(IQ,SQ,fQ,optQ)NPQFPTASQPFPT

PFPT

NPQPFPTO(|x|O(1)kO(1))|x|x

Outras caracterizações para duas classes de aproximação são propostas em [2, Teorema 6.5].

Um problema é

  • PTASptasXPw

  • FPTASfptasPFPTw

(f)ptas(XP)PFPTw1ϵ and bounding from below an optimum value.

  1. Polynomial time approximation schemes and parameterized complexity. J. Chen et al. / Discrete Applied Mathematics 155 (2007) 180 – 193.
  2. Structure of Polynomial-Time Approximation. E. J. van Leeuwen et al. Technical Report UU-CS-2009-034, December 2009.
Oleksandr Bondarenko
fonte