Considere o problema de conjunto dominante em gráficos gerais e seja o número de vértices em um gráfico. Um algoritmo de aproximação ganancioso fornece uma garantia de aproximação do fator , ou seja, é possível encontrar em tempo polinomial uma solução tal que , em que é o tamanho de um conjunto dominante mínimo. Há limites que mostram que não podemos melhorar a dependência muito http://www.cs.duke.edu/courses/spring07/cps296.2/papers/p634-feige.pdf .1 + log n S | S | ≤ ( 1 + log n ) o p t o p t log n
Minha pergunta: existe um algoritmo de aproximação que tenha uma garantia em termos de vez de ? Nos gráficos em que é muito grande em relação ao ótimo, uma aproximação fator- seria muito pior que uma aproximação fator- . É conhecido algo assim ou existem razões pelas quais isso não pode existir? Estou satisfeito com qualquer algoritmo de tempo polinomial que produz uma solução tal que para alguma constante .n n log n log o p t S | S | ∈ O ( o p t c ) c
Isso deve ser um comentário, pois não responde diretamente à sua pergunta, mas uma pergunta relacionada. Talvez um truque semelhante de [1] forneça uma resposta.
Em [1] o seguinte é comprovado:
[1] Rodney G. Downey, Michael R. Fellows, Catherine McCartin e Frances Rosamond. "Aproximação parametrizada de problemas de conjuntos dominantes". Information Processing Letters, Volume 109 - Edição 1, dezembro de 2008.
fonte