Consecuencias de los límites inferiores para las redes

10

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 }{(X,R)XRX}

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?fϵf(1/ϵ)

James King
fuente
2
hay un nuevo resultado que tiene límites inferiores aún más fuertes: arxiv.org/abs/1012.1240
Suresh Venkat

Respuestas:

7

ϵf(1/ϵ)f(1/ϵ)/(1/ϵ)

ϵ

Sariel Har-Peled
fuente
ϵO(K/ϵ)K
1
Teorema 1 en el documento ...
Sariel Har-Peled
5

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

Suresh Venkat
fuente