¿Existencia de

Considere el problema del conjunto dominante en gráficos generales, y sea el número de vértices en un gráfico. Un algoritmo de aproximación codicioso ofrece una garantía de aproximación del factor 1 + log n , es decir, es posible encontrar en el tiempo polinómico una solución S tal que | S | ≤ ( 1 + log n ) o p t , donde o p t es el tamaño de un conjunto dominante mínimo. Hay límites que muestran que no podemos mejorar la dependencia de registro n mucho$n$$1 + \log n$$S$$|S| \leq (1 + \log n) opt$$opt$$\log n$http://www.cs.duke.edu/courses/spring07/cps296.2/papers/p634-feige.pdf .

Mi pregunta: ¿hay un algoritmo de aproximación que tenga una garantía en términos de lugar de n ? En los gráficos donde n es muy grande con respecto al óptimo, una aproximación factor- log n sería mucho peor que una aproximación factor log o p t . ¿Se sabe algo así o hay razones por las que esto no puede existir? Estoy contento con cualquier algoritmo de tiempo polinómico que produzca una solución S tal que | S | ∈ O ( o p t c ) para alguna constante $opt$$n$$n$$\log n$$\log opt$$S$$|S| \in O(opt^c)$$c$.

Creo que todavía está abierto si Dominating Set o Hitting Set tienen una aproximación af (OPT) para alguna función (no trivial) f. Esta debería ser una pregunta muy difícil (y posiblemente profunda) de responder. Considero que es la pregunta más emocionante en aproximación parametrizada (junto con la pregunta análoga para Clique). Es posible que desee echar un vistazo a mi encuesta [1] que analiza esto. Tenga en cuenta que se muestra en el documento más reciente [2] que "la capacidad de un circuito monótono para los circuitos de trama-2", un problema que es más general que el conjunto dominante, no tiene una aproximación f (OPT) para ninguna f.

[1] D. Marx. Complejidad parametrizada y algoritmos de aproximación. The Computer Journal, 51 (1): 60-78, 2008.

[2] D. Marx. Problemas parametrizados completamente monótonos y antimonotónicos. En Actas de la 25a Conferencia Anual de IEEE sobre Complejidad Computacional, Cambridge, Massachusetts, 181-187, 2010.

Esto debería ser un comentario, ya que no responde directamente a su pregunta, sino una pregunta relacionada. Tal vez ese truco similar de [1] le proporcione una respuesta.

En [1] se demuestra lo siguiente:

$G=(V,E)$$k$$k$$G$$g(k)$$g(k)$$k$$G$$k$

$g(k)$

[1] Rodney G. Downey, Michael R. Fellows, Catherine McCartin y Frances Rosamond. "Aproximación parametrizada de problemas de conjuntos dominantes". Information Processing Letters, Volumen 109, Edición 1, diciembre de 2008.