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ę:
: jest skończonym zestawem punktów planarnych, zawiera wszystkie przecięcia z liniami
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?
Odpowiedzi:
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.ϵ
źródło
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),
źródło