Co wiadomo na temat następującego problemu?
Biorąc pod uwagę zbiór funkcji f : { 0 , 1 } n → { 0 , 1 } , znajdź największą podkolekcję S ⊆ C z zastrzeżeniem ograniczenia, że VC-Wymiar ( S ) ≤ k dla jakiejś liczby całkowitej k .
Czy istnieją algorytmy aproksymacyjne lub wyniki twardości dla tego problemu?
Odpowiedzi:
Edycja : pierwotny problem to - twardy do przybliżenia, gdy k = 1 gdzie n oznacza liczbę zbiorów.n1−ϵ k=1 n
W dualności pierwotny problem (dla ) jest równoważny, biorąc pod uwagę hypergraph ( V , S ) , znajdź maksymalny rozmiar U ⊆ V przy ( U , { S ∩ U ∣ S ∈ S } ) bezkrzyżowym.k=1 (V,S) U⊆V (U,{S∩U∣S∈S})
W rzeczywistości ten (podwójny) problem jest bardzo trudny, nawet jeśli wszystkie zestawy w mają rozmiar 2: wtedy jest to wykres i szukamy maksymalnego rozmiaru wierzchołka, którego indukowany podgraf, który nie zawiera ścieżki o dwóch krawędziach ( nietrudno zauważyć, że jest to jedyny sposób na powstanie krzyżującej się pary, zakładając, że wykres ma co najmniej 4 wierzchołki). Ale ta właściwość jest dziedziczna i nietrywialna, dlatego możemy użyć wyniku Feige i Kogana do wykazania twardości.S
Oryginalna odpowiedź
Ale w przypadku pierwotnego (pierwotnego) problemu wydaje się, że potrzeba więcej przemyśleń ... wygląda interesująco!
źródło
Niektóre istotne powiązane prace: Szacowanie samego wymiaru VC (nie mówiąc już o znalezieniu dużego podkolekcji z ograniczonym wymiarem VC) w twojej reprezentacji jest uzupełnieniem LOGNP (LOGNP jest NP ograniczony do log n bitów niedeterminizmu). Jest również trochę powiązanych prac dotyczących szacowania i aproksymacji wymiaru VC, gdy prezentacja przestrzeni zasięgu jest bardziej zwarta (patrz również odnośniki w środku)
źródło