Cubierta del conjunto de frecuencia limitada de cardinalidad limitada: dureza de aproximación

26

Considere el problema de cobertura de conjunto mínimo con las siguientes restricciones: cada conjunto contiene como máximo k elementos y cada elemento del universo se produce en la mayoría de los conjuntos f .

  • Ejemplo: el caso k=4 y f=2 es equivalente al problema cobertura mínima vértice en gráficos con el máximo grado 4.

Deje a(k,f)>1 sea el valor más grande de tal manera que la búsqueda de una a(k,f) : Aproximación del conjunto mínimo problema de cobertura con los parámetros k y f es NP-duro.

Pregunta: ¿Tenemos una referencia que resume los límites inferiores más fuertes conocidos en a(k,f) ? En particular, estoy interesado en valores concretos en el caso de que k y f sean pequeños pero f>2 .


Las versiones restringidas del problema de cobertura del conjunto a menudo son convenientes en las reducciones; por lo general, hay cierta libertad para elegir los valores de k y f , y más información sobre a(k,f) ayudaría a elegir los valores correctos que brinden los resultados de dureza más sólidos. Las referencias aquí , aquí y aquí proporcionan un punto de partida, pero la información es algo obsoleta y fragmentaria. Me preguntaba si hay una fuente más completa y actualizada.

Jukka Suomela
fuente
¡Gracias por las respuestas hasta ahora! Comencemos una recompensa y veamos si podemos obtener más participación. En aras de la concreción, estaré encantado de otorgar la recompensa si alguien da un puntero a un límite inferior no trivial en a(3,3) .
Jukka Suomela
... y la recompensa fue a la respuesta que dio algo que estaba más cerca de un límite inferior en a(3,3) , pero en aras de la equidad, decidí aceptar la respuesta más completa. Gracias a todos; parece que el caso de a(3,3) está abierto.
Jukka Suomela

Respuestas:

15

Usando la notación de parámetro más común lugar de ( k , f ) , esto es equivalente (y creo que más comúnmente conocido como) el problema de la cubierta de vértices en hipergrafías k- uniformes de grado máximo Δ . Para enfatizar, por coherencia con la literatura, estoy usando k donde usas f , y Δ donde usas k .(Δ,k)(k,f)kΔkfΔk

Para cualquier constante , los resultados que ignoran Δ incluyenε>0Δ

  • supΔ{a(Δ,k)}k
  • supΔ{a(Δ,k)}k1ε (Dinur et al., 2004) , como señaló Lev.
  • Si la conjetura de los juegos únicos es cierta, entonces , que es estricta (Khot y Regev, 2008) .supΔ{a(Δ,k)}kε

Ignorando ,k

  • supk{a(Δ,k)}Δ (trivial).
  • supk{a(4,k)}2ε (Holmerin, 2002)

El único resultado que sé que combina los dos parámetros es

  • a(Δ,k)k(1o(1))(k(k1)lnlnΔln(Δ)) para fijo , o creciendo lentamente con (Halperin, 2002)kkΔ

Existe una conexión entre este problema y el problema del Conjunto independiente (débil), pero no estoy exactamente seguro de cómo están relacionados en términos de aproximabilidad. Recomendaría investigar esto, quizás comenzando aquí: [PDF] .

James King
fuente
Gracias por los punteros y disculpas por usar los parámetros algo confusos. (Traté de ser coherente con el uso del parámetro en la " cubierta mínima de set", y decidí seguir la notación utilizada en el libro de Vazirani).kk
Jukka Suomela
12

Usando, como en la respuesta de James King, la notación para la mejor aproximación del tiempo polinomial posible de la cubierta del vértice en hipergrafías uniformes de grado como máximo , también tenemosa(Δ,k)kΔ

(1)a(Δ,k)lnΔ+O(1)

del algoritmo de aproximación codicioso para la cobertura del conjunto: la cobertura del vértice en hipergrafías de grado como máximo es el mismo que el problema de la cobertura del conjunto con conjuntos de tamaño como máximo , para el cual el algoritmo codicioso tiene una relación de aproximación como máximo , donde es la función armónica.Δ H Δ H n = 1 + 1 / 2 + ... 1 / n ln n + O ( 1 )ΔΔHΔHn=1+1/2+1/nlnn+O(1)

En este artículo muestro que

(2)supk{a(Δ,k)}lnΔO(lnlnΔ)

a menos que , cambiando los parámetros en una reducción de Feige.P=NP

Luca Trevisan
fuente
7

Por si acaso no lo encontraste; El resultado de dureza más reciente para la cubierta de vértice de grado acotado que encontré en una búsqueda reciente es Chlebik y Chlebikova , por ejemplo, aproximadamente 1.01 de dureza en gráficos cúbicos.

daveagp
fuente
6

Esto no responde a su pregunta, pero quizás pueda ayudarlo: hay un documento [Dinur et al. 2004] que cubre f> 2 (pero parece que no arregla k).

Lev Reyzin
fuente