Estoy interesado en la complejidad parametrizada de lo que llamaré el problema d-Dimensional Hitting Set: dado un espacio de rango (es decir, un sistema / hipergrafía establecido) S = (X, R) que tiene una dimensión VC como máximo d y a entero positivo k, ¿contiene X un subconjunto de tamaño k que alcanza cada rango en R? La versión parametrizada del problema está parametrizada por k.
¿Para qué valores de d es el problema d-Dimensional Hitting Set?
- en FPT?
- en W [1]?
- W [1] -duro?
- W [2] -duro?
Lo que sé se puede resumir de la siguiente manera:
El Conjunto de Golpes 1-Dimensional está en P y, por lo tanto, en FPT. Si S tiene dimensión 1, entonces no es difícil demostrar que hay un conjunto de golpes de tamaño 2 o que la matriz de incidencia de S está totalmente equilibrada. En cualquier caso, podemos encontrar un conjunto mínimo de golpes en el tiempo polinómico.
El conjunto de golpes de 4 dimensiones es W [1] duro. Dom, Fellows y Rosamond [PDF] demostraron una dureza W [1] para el problema de apuñalar rectángulos paralelos al eje en R ^ 2 con líneas paralelas al eje. Esto puede formularse como Hitting Set en un espacio de rango de VC-dimension 4.
Si no se establece ninguna restricción en d, entonces tenemos el problema estándar de conjunto de golpes que es W [2] -completo y NP-completo.
Langerman y Morin [citeseer link] dan algoritmos FPT para Set Cover en dimensión restringida, aunque su modelo de dimensionalidad limitada no es el mismo que el modelo definido por la dimensión VC limitada. Su modelo no parece incluir, por ejemplo, el problema de golpear medios espacios con puntos, aunque el problema prototipo para su modelo es equivalente a golpear hiperplanos con puntos.
Respuestas:
Creo que este problema es muy difícil. No sabemos la respuesta a problemas mucho más fáciles en esta familia. Por ejemplo, dado un conjunto de n puntos en el plano y un conjunto de (por ejemplo, n) discos unitarios, decida si hay una cobertura de los puntos por k de los discos unitarios. Hay un algoritmo de tiempo n ^ O (k) fácil para esto, y no me sorprendería si usando conocimientos conocidos se puede hacer n ^ O (sqrt {k}) (pero incluso eso no es obvio), pero hacer f ( k) * n ^ {O (1)} está abierto, y de hecho sería bastante interesante. Una aproximación (1 + eps) se desprende del trabajo de Mustafa y Ray http://portal.acm.org/citation.cfm?id=1542362.1542367 .
Por cierto, para la versión continua donde se permite cualquier unidad de disco, se puede resolver el problema en n ^ {O (k)} tiempo. Un PTAS en este caso también es bastante fácil usando cuadrículas desplazadas.
fuente
Abordamos esta pregunta en un nuevo preprint: http://arxiv.org/abs/1512.00481
Conjunto de golpes en hipergrafías de baja dimensión VC (Karl Bringmann, László Kozma, Shay Moran, NS Narayanaswamy).
Resulta que Hitting Set es W [1] -duro cuando la dimensión VC es igual a 2.
fuente
El artículo Dániel Marx: ¿ Esquemas de aproximación eficiente para problemas geométricos ? ESA 2005: 448-459 es bastante relevante.
fuente