Szacowanie wymiaru VC

12

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 .Cf:{0,1}n{0,1}SC(S)kk

Czy istnieją algorytmy aproksymacyjne lub wyniki twardości dla tego problemu?

Aaron Roth
źródło
Funkcje wydają się nie odgrywać żadnej roli w maksymalizacji | S |
Suresh Venkat
Wybór funkcji determinuje wymiar VC S. Problem polega na znalezieniu jak największej klasy funkcji, z zastrzeżeniem ograniczenia wymiaru VC.
Aaron Roth,
Widzę. Przetłumaczone na „obszar geometrii”, otrzymujesz zbiór zakresów (f działa jako funkcja charakterystyczna) i chcesz mieć największą podgrupę ograniczonego wymiaru VC.
Suresh Venkat
Drugi problem w odpowiedzi na pytanie: jak przedstawia się C? Wiemy, że maksymalny możliwy rozmiar wynosi O ( 2 n k ) według Lemera Sauera, a zapisanie nawet jednej funkcji w C wymaga n bitów. SO(2nk)Cn
Suresh Venkat
1
Dobrze. Interesują mnie wyniki w dowolnym systemie reprezentacyjnym. Można sobie wyobrazić, że jest przedstawione jako 2 n × | C | macierz, w którym to przypadku czas działania 2 n × | C | byłby `` efektywny '' (choć nie czas 2 n × k , co wystarczyłoby, aby wyczerpująco sprawdzić, czy wszystkie zbiory k punktów zostały rozbite). Jeśli jakiekolwiek wyniki algorytmu są możliwe przy jedynie dostępnym zapytaniu do czarnej skrzynki do funkcji w C , byłoby to jeszcze lepsze. C2n×|C|2n×|C|2n×kkC
Aaron Roth

Odpowiedzi:

7

Edycja : pierwotny problem to - twardy do przybliżenia, gdy k = 1 gdzie n oznacza liczbę zbiorów.n1ϵk=1n

P,QAPQ,PQ,QP,(PQ)c

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)UV(U,{SUSS})

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ź

k=1SSn1ϵΘ(n)

AP,QAPQ,PQ,QP,(PQ)c

G=(V,E)H=(X,S)X=VE{0}0vGTvS

{v}{ee is an edge incident to v}.

{Tv}vUUG

Ale w przypadku pierwotnego (pierwotnego) problemu wydaje się, że potrzeba więcej przemyśleń ... wygląda interesująco!

daveagp
źródło
4

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)

Suresh Venkat
źródło