Muchos aquí probablemente estén al tanto de los límites inferiores súper lineales recientes de Alon para redes en un entorno geométrico natural [PDF] . Me gustaría saber qué implica, en todo caso, un límite inferior acerca de la aproximación de los problemas asociados de Set Cover / Hitting Set.
Para ser un poco más específico, considere una familia de espacios de distribución, por ejemplo, la familia:
:Xes un conjunto de puntos planos finitos,Rcontiene todas las intersecciones deXcon líneas }
Si, para alguna función que es lineal o superlineal , la familia contiene un espacio de rango que no admite redes ϵ de tamaño f ( 1 / ϵ ) , ¿qué implica esto, en todo caso, sobre el problema del conjunto de golpes mínimos? restringido a esta familia de espacios de distribución?
Respuestas:
fuente
No estoy seguro de que implique algo. Los resultados principales fluyen en la otra dirección, es decir, por las construcciones Bronnimann / Goodrich o Even / Rawitz / Shahar , una red de tamaño lineal implica una aproximación de factor constante para el conjunto de golpes (para la dimensión VC acotada),
fuente