Estou interessado na complexidade parametrizada do que chamarei de problema do conjunto de batida d-dimensional: dado um espaço de intervalo (isto é, um sistema definido / hipergrafo) S = (X, R) tendo a dimensão VC no máximo d e um número inteiro positivo k, X contém um subconjunto de tamanho k que atinge todos os intervalos em R? A versão parametrizada do problema é parametrizada por k.
Para quais valores de d é o problema do conjunto de batidas d-Dimensional
- no FPT?
- em W [1]?
- W-1-difícil?
- W [2] -hard?
O que eu sei pode ser resumido da seguinte forma:
O conjunto de batidas unidimensionais está em P e, portanto, em FPT. Se S tem a dimensão 1, não é difícil mostrar que existe um conjunto de tamanho 2 ou a matriz de incidência de S é totalmente equilibrada. Em ambos os casos, podemos encontrar um conjunto mínimo de batidas no tempo polinomial.
O conjunto de batidas em 4 dimensões é W [1] -hard. Dom, Fellows e Rosamond [PDF] provaram a dureza W [1] para o problema de esfaquear retângulos paralelos ao eixo em R ^ 2 com linhas paralelas ao eixo. Isso pode ser formulado como conjunto de batidas em um espaço de intervalo da dimensão 4 do VC.
Se nenhuma restrição for colocada em d, teremos o problema padrão do Conjunto de Acertos, que é W [2] -complete e NP-complete.
Langerman e Morin [citeseer link] fornecem algoritmos FPT para Set Cover em dimensão restrita, embora seu modelo de dimensionalidade limitada não seja o mesmo que o modelo definido pela dimensão VC limitada. Seu modelo não parece incluir, por exemplo, o problema de acertar meios espaços com pontos, embora o problema do protótipo para seu modelo seja equivalente a atingir hiperplanos com pontos.
Respostas:
Eu acho que esse problema é muito difícil. Não sabemos a resposta para problemas muito mais fáceis nesta família. Por exemplo, dado um conjunto de n pontos no plano e um conjunto de (digamos n) discos de unidade, decida se existe uma cobertura dos pontos por k dos discos de unidade. Existe um algoritmo de tempo n ^ O (k) fácil para isso, e eu não ficaria surpreso se, usando idéias conhecidas, é possível fazer n ^ O (sqrt {k}) (mas mesmo isso não é óbvio), mas fazendo f ( k) * n ^ {O (1)} está aberto e, de fato, seria bastante interessante. Uma aproximação (1 + eps) segue o trabalho de Mustafa e Ray http://portal.acm.org/citation.cfm?id=1542362.1542367 .
BTW, para a versão contínua em que qualquer disco de unidade é permitido, é possível resolver o problema em n ^ {O (k)} tempo. Um PTAS neste caso também é bastante fácil usando grades deslocadas.
fonte
Abordamos esta questão em uma nova pré-impressão: http://arxiv.org/abs/1512.00481
Hitting Set em hipergrafos de baixa dimensão VC (Karl Bringmann, László Kozma, Shay Moran, NS Narayanaswamy).
Acontece que Hitting Set já é W [1] quando a dimensão VC é igual a 2.
fonte
O artigo Dániel Marx: Esquemas de Aproximação Eficientes para Problemas Geométricos ? SEC 2005: 448-459 é bastante relevante.
fonte