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 k
Existem algoritmos de aproximação ou resultados de dureza para esse problema?
Respostas:
Editar : o problema original é - difícil de aproximar quando k = 1, em que n indica o número de conjuntos.n1 - ϵ k = 1 n
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,Q A P∩Q,P∖Q,Q∖P,(P∪Q)c
Resposta original
Mas, para o problema original (primordial), parece que é necessário pensar um pouco mais ... parece interessante!
fonte
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)
fonte