Consequências de limites inferiores para

10

Muitos aqui provavelmente estão cientes dos recentes limites inferiores super-lineares de Alon para redes em uma configuração geométrica natural [PDF] . Gostaria de saber o que, se é que existe alguma coisa, um limite tão baixo implica na proximidade dos problemas associados ao conjunto de tampa / conjunto de batidas. ϵ

Para ser um pouco mais específico, considere uma família de espaços de intervalo, por exemplo, a família:

{(X,R) : é um conjunto de pontos planares finitos, contém todas as interseções de com as linhasXRX}

Se, para alguma função que é linear ou super-linear, a família contiver um espaço de intervalo que não admite redes de tamanho , o que, se houver alguma coisa, isso implica no Acerto Mínimo Definir problema restrito a essa família de espaços de intervalo?fϵf(1/ϵ)

James King
fonte
2
há um novo resultado com limites inferiores ainda mais fortes: arxiv.org/abs/1012.1240
Suresh Venkat

Respostas:

7

Se um espaço de intervalo tiver -net do tamanho , o intervalo de integralidade do conjunto de batidas fracionárias (ou tampa do conjunto) será . Veja o trabalho de Philip Long ( aqui [o trabalho de The Even et al. É posterior a este trabalho e redescobre algumas de suas coisas]). Veja também os slides 13-16 aqui .f ( 1 / ϵ ) f ( 1 / ϵ ) / ( 1 / ϵ )ϵf(1 1/ϵ)f(1 1/ϵ)/(1 1/ϵ)

Em resumo, ter redes não lineares indica que aproximar o problema relevante da cobertura do conjunto de batidas / conjuntos dentro de um fator melhor que um fator constante será muito desafiador.ϵ

Sariel Har-Peled
fonte
Qual seção do primeiro artigo é relevante para esse problema em particular? Ou, de maneira equivalente, no segundo link, você diz "Em configurações geométricas, há uma de tamanho se o intervalo de integralidade for ". Estou tendo problemas para entender isso. O ( K / ϵ ) KϵO(K/ϵ)K
taninamdar 23/10
11
Teorema 1 no jornal ...
Sariel Har-Peled
5

Não tenho certeza se isso implica alguma coisa. Os principais resultados fluem na outra direção, ou seja, pelas construções Bronnimann / Goodrich ou Even / Rawitz / Shahar , uma rede de tamanho linear implica uma aproximação constante de fatores para o conjunto de acertos (para a dimensão de CV limitada),

Suresh Venkat
fonte