Les conséquences de limites inférieures de

Beaucoup ici sont probablement au courant de la baisse super-linéaire limite récente pour Alon -nets dans un cadre géométrique naturel [PDF] . Je voudrais savoir ce que, le cas échéant, une telle borne inférieure implique au sujet de l'approximation des problèmes de jeu de couverture / jeu de frappe associés. $\epsilon$

Pour être un peu plus précis, considérons une famille d'espaces de gamme, par exemple, la famille:

:Xest un ensemble de points planaires finis,Rcontient toutes les intersections deXavec des lignes$\big\{(X,\mathcal{R})$$X$$\mathcal{R}$$X$$\big\}$

Si, pour une fonction qui est linéaire ou super-linéaire, la famille contient un espace de plage qui n'admet pas ϵ -réseaux de taille f ( 1 / ϵ ) , qu'est-ce que cela implique, le cas échéant, à propos du problème de l'ensemble de frappe minimum limité à cette famille d'espaces de gamme?$f$$\epsilon$$f(1/\epsilon)$

Si un espace de gamme a -net de taille f ( 1 / ε ) , l'écart de l' intégralité de l'ensemble de frappe fractionnaire (ou couvercle set) est f ( 1 / ε ) / ( 1 / ε ) . Voir le travail de Philip Long ( ici [Le travail Even et al. Est plus tard que ce travail, et redécouvrir certains de ses trucs]). Voir également les diapositives 13-16 ici .$\epsilon$$f(1/\epsilon)$$f(1/\epsilon)/(1/\epsilon)$

En bref, avoir des filets non linéaires , indique qu'il sera très difficile d'approcher le problème de couverture par ensemble de frappes / ensemble à l'intérieur d'un facteur supérieur à un facteur constant.$\epsilon$

Je ne suis pas sûr que cela implique quoi que ce soit. Les principaux résultats découlent dans l'autre sens, c'est-à-dire par les constructions Bronnimann / Goodrich ou Even / Rawitz / Shahar , un filet de taille linéaire implique une approximation de facteur constant pour l'ensemble de frappe (pour la dimension VC bornée),