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

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.

• Ejemplo: $a(4,2) \ge 1.0128$ ( Berman y Karpinski 1999 ).

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.

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 .$(\Delta,k)$$(k,f)$$k$$\Delta$$k$$f$$\Delta$$k$

Para cualquier constante , los resultados que ignoran Δ incluyen$\varepsilon > 0$$\Delta$

• $\sup_\Delta\{ a(\Delta,k) \}\leq k$
• $\sup_\Delta\{ a(\Delta,k) \}\geq k-1-\varepsilon$ (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_\Delta \{a(\Delta,k)\} \geq k-\varepsilon$

Ignorando ,$k$

• $\sup_k\{ a(\Delta,k) \}\leq \Delta$ (trivial).
• $\sup_k\{ a(4,k) \}\geq 2-\varepsilon$ (Holmerin, 2002)

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

• $a(\Delta,k) \leq k - (1-o(1))\left(\frac{k(k-1)\ln\ln\Delta}{\ln(\Delta)}\right)$ para fijo , o creciendo lentamente con (Halperin, 2002)$k$$k$$\Delta$

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] .

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 tenemos$a(\Delta,k)$$k$$\Delta$

(1)$a(\Delta,k) \leq \ln \Delta + 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 $\Delta$$\Delta$$H_\Delta$$H_n = 1 + 1/2 + \ldots 1/n \leq \ln n + O(1)$

En este artículo muestro que

(2)$\sup_k \{ a(\Delta ,k) \} \geq \ln \Delta - O(\ln\ln \Delta)$

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

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.

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).