Konsekwencje dolnych granic dla -net na przybliżeniu

Wielu tutaj prawdopodobnie zdaje sobie sprawę z ostatnich superliniowych dolnych granic Alon dla -net w naturalnych ustawieniach geometrycznych [PDF] . Chciałbym wiedzieć, co, jeśli w ogóle, taka dolna granica implikuje przybliżenie powiązanych problemów z zestawem Cover / Hitting Set. $\epsilon$

Aby być nieco bardziej szczegółowym, rozważ rodzinę przestrzeni zasięgu, na przykład rodzinę:

$\big\{(X,\mathcal{R})$ : jest skończonym zestawem punktów planarnych, zawiera wszystkie przecięcia z liniami$X$$\mathcal{R}$$X$$\big\}$

Jeśli dla jakiejś funkcji która jest liniowa lub superliniowa , rodzina zawiera przestrzeń zakresu, która nie dopuszcza sieci o rozmiarze , co w ogóle oznacza to z minimalnym uderzeniem Czy problem jest ograniczony do tej rodziny przestrzeni zasięgu?$f$$\epsilon$$f(1/\epsilon)$

Jeśli przestrzeń zakresu ma -net o rozmiarze , to szczelność integralności ułamkowego zestawu uderzeń (lub zestawu osłon) wynosi . Zobacz pracę Philipa Longa ( tutaj [Praca parzysta i późniejsza jest późniejsza niż ta i odkrywasz niektóre z jego rzeczy]). Zobacz także slajdy 13-16 tutaj .$\epsilon$$f(1/\epsilon)$$f(1/\epsilon)/(1/\epsilon)$

Krótko mówiąc, posiadanie nieliniowych sieci wskazuje, że przybliżenie odpowiedniego problemu z zestawem uderzeń / zestawów uderzeń w ramach lepszych niż stały czynnik będzie bardzo trudne.$\epsilon$

Nie jestem pewien, czy to coś sugeruje. Główne wyniki płyną w innym kierunku, tj. Przez konstrukcje Bronnimann / Goodrich lub Even / Rawitz / Shahar , liniowa wielkość siatki implikuje stałe przybliżenie współczynnika dla zestawu uderzeń (dla ograniczonego wymiaru VC),