Interesuje mnie sparametryzowana złożoność problemu, który nazywam d-Dimensional Hitting Set: biorąc pod uwagę przestrzeń zakresu (tj. Układ zestawu / hipergraph) S = (X, R) mający wymiar VC co najwyżej d dodatnia liczba całkowita k, czy X zawiera podzbiór wielkości k, który uderza w każdy zakres w R? Sparametryzowana wersja problemu jest parametryzowana przez k.
Dla jakich wartości d jest problemem d-Dimensional Hitting Set
- w FPT?
- w W [1]?
- W [1] - twardy?
- W [2] - twardy?
To, co wiem, można streścić w następujący sposób:
1-wymiarowy zestaw uderzeń jest w P, a zatem w FPT. Jeśli S ma wymiar 1, nie jest trudno wykazać, że albo istnieje zestaw uderzeń o rozmiarze 2, albo macierz występowania S jest całkowicie zrównoważona. W obu przypadkach możemy znaleźć minimalny zestaw uderzeń w czasie wielomianowym.
4-wymiarowy zestaw uderzeniowy ma twardość W [1]. Dom, Fellows i Rosamond [PDF] udowodnili twardość W [1] dla problemu przebijania prostokątów równoległych do osi w R ^ 2 liniami równoległymi do osi. Można to sformułować jako zestaw uderzeniowy w przestrzeni zasięgu wymiaru VC 4.
Jeśli żadne ograniczenie nie zostanie nałożone na d, mamy standardowy problem z zestawem uderzeń, który jest W-2-kompletny i NP-kompletny.
Langerman i Morin [link do cytatu] podają algorytmy FPT dla opcji Ustaw osłonę w ograniczonym wymiarze, chociaż ich ograniczony model wymiarowy nie jest taki sam jak model zdefiniowany przez ograniczony wymiar VC. Wydaje się, że ich model nie obejmuje na przykład problemu trafiania półprzestrzeni punktami, chociaż problem prototypowy dla ich modelu jest równoważny trafianiu w hiperpłaszczyzny punktami.
Odpowiedzi:
Myślę, że ten problem jest zbyt trudny. Nie znamy odpowiedzi na znacznie łatwiejsze problemy w tej rodzinie. Na przykład, biorąc pod uwagę zestaw n punktów na płaszczyźnie i zestaw (powiedzmy n) dysków jednostkowych, zdecyduj, czy istnieje pokrywa punktów przez k dysków jednostkowych. Jest do tego łatwy algorytm czasu n ^ O (k) i nie zdziwiłbym się, gdyby wykorzystując znane spostrzeżenia można zrobić n ^ O (sqrt {k}) (ale nawet to nie jest oczywiste), ale wykonując f ( k) * n ^ {O (1)} jest otwarty i faktycznie byłby całkiem interesujący. Przybliżenie (1 + eps) wynika z pracy Mustafa i Raya http://portal.acm.org/citation.cfm?id=1542362.1542367 .
BTW, dla wersji ciągłej, w której dozwolony jest dowolny dysk jednostkowy, problem można rozwiązać w czasie n ^ {O (k)}. PTAS w tym przypadku jest również dość łatwy przy użyciu przesuniętych siatek.
źródło
Odpowiadamy na to pytanie w nowym przedruku: http://arxiv.org/abs/1512.00481
Zestaw uderzeniowy w hipergrrafach o niskim wymiarze VC (Karl Bringmann, László Kozma, Shay Moran, NS Narayanaswamy).
Okazuje się, że zestaw uderzeń ma twardość W [1] już wtedy, gdy wymiar VC jest równy 2.
źródło
Artykuł Dániel Marks: Skuteczne schematy aproksymacyjne dla problemów geometrycznych ? ESA 2005: 448–459 jest dość istotny.
źródło