Quão intrínseco é o termo

8

Uma rede para um espaço de intervalo ( X , R ) é um subconjunto N de X, de modo que N R não é vazio para todos os R R, de modo que | X R | ε | X | .ε(X,R)NXNRRR|XR|ε|X|

Dado um espaço de alcance da dimensão VC d , uma rede ε do tamanho O ( d(X,R)dεpode ser calculado no tempoO(d)3d(1O(dεlog(dε))(veja [1], Thm 4.6).O(d)3d(1ε2log(dε))d|X|

Até que ponto o termo intrínseco a esse problema? Especificamente, pode ser melhorado para 2 O ( d ) ? Existem limites inferiores conhecidos?O(d)3d2O(d)

Uma questão relacionada: existem condições gerais em para as quais se sabe que existe essa melhoria?(X,R)

[1] Bernard Chazelle. O método da discrepância. 2000.

Don Sheehy
fonte
2
Boa pergunta ! e seja bem-vindo, Don!
Suresh Venkat

Respostas:

10

O((d/ϵ)log(d/ϵδ))ϵ1δ

dO(d)s=O((d/ϵ)log(d/ϵ))sϵ2sO((2s)d)sddO(d)dsd

Jeff Phillips
fonte