Estimando a dimensão VC

12

O que se sabe sobre o seguinte problema?

Dada uma coleção de funções , encontre a maior sub-coleção sujeita à restrição de que VC-Dimension para algum número inteiro .f : { 0 , 1 } n{ 0 , 1 } S C ( S ) k kCf:{0,1}n{0,1}SC(S)kk

Existem algoritmos de aproximação ou resultados de dureza para esse problema?

Aaron Roth
fonte
As funções parecem não ter papel na maximização | S |
Suresh Venkat
A escolha das funções determina a dimensão VC de S. O problema é encontrar uma classe de funções tão grande quanto possível, sujeita a uma restrição de dimensão VC.
Aaron Roth
Entendo. Assim, traduzido para "geometria da terra", você recebe uma coleção de intervalos (f atua como uma função característica) e deseja uma maior sub-coleção da dimensão de VC limitada.
Suresh Venkat 22/02
O outro problema em responder à pergunta: como é apresentado C? Sabemos que o tamanho máximo possível de é O ( 2 n k ) pelo Lema de Sauer, e escrever uma única função em C requer n bits. SO(2nk)Cn
Suresh Venkat 22/02
1
Certo. Estou interessado em resultados em qualquer regime representacional. Você pode imaginar que é apresentado como um 2 n × | C | matriz, caso em que o tempo de execução 2 n × | C | seria `` eficiente '' (embora não seja o tempo 2 n × k , o que seria necessário para verificar exaustivamente se todas as coleções de k pontos foram destruídas). Se algum resultado algorítmico for possível com apenas acesso à consulta de caixa preta para as funções em C , isso seria ainda melhor. C2n×|C|2n×|C|2n×kkC
Aaron Roth

Respostas:

7

Editar : o problema original é - difícil de aproximar quando k = 1, em que n indica o número de conjuntos.n1ϵk=1n

O dual de um hipergrafo é obtido trocando vértices por arestas e preservando incidências. É mais fácil entender o problema quando observamos que um hipergrafo possui a dimensão 1 de VC, se o seu duplo for livre de cruzamentos (para todos os em A , pelo menos um de P Q , P Q , Q P , ( P Q ) c está vazio).P,QAPQ,PQ,QP,(PQ)c

k=1(V,S)UV(U,{SUSS})

S

Resposta original

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

Mas, para o problema original (primordial), parece que é necessário pensar um pouco mais ... parece interessante!

daveagp
fonte
4

Algum trabalho relacionado relevante: estimar a própria dimensão VC (sem falar em encontrar uma subcoleção grande com dimensão VC limitada) em sua representação é LOGNP-complete (LOGNP é NP restrito ao log n bits de não-determinismo). Também há um pouco de trabalho relacionado sobre estimativa e aproximação da dimensão VC, quando a apresentação do espaço do intervalo é mais compacta (consulte também as referências)

Suresh Venkat
fonte