Konsekwencje dolnych granic dla -net na przybliżeniu

10

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. ϵ

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

{(X,R) : jest skończonym zestawem punktów planarnych, zawiera wszystkie przecięcia z liniamiXRX}

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

James King
źródło
2
pojawia się nowy wynik, który ma jeszcze silniejsze dolne granice: arxiv.org/abs/1012.1240
Suresh Venkat

Odpowiedzi:

7

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

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.ϵ

Sariel Har-Peled
źródło
Która sekcja pierwszego artykułu dotyczy tego konkretnego problemu? Lub równoważnie, w drugim łączu powiesz „W ustawieniach geometrycznych istnieje -net o rozmiarze jeśli różnica integralności wynosi ”. Mam problem ze zrozumieniem tego. ϵO(K/ϵ)K
taninamdar
1
Twierdzenie 1 w pracy ....
Sariel Har-Peled
5

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

Suresh Venkat
źródło