Je m'intéresse à la complexité paramétrée de ce que j'appellerai le problème d'ensemble d-dimensionnel: donné un espace de plage (c'est-à-dire un ensemble système / hypergraphe) S = (X, R) ayant une dimension VC au plus d et a entier positif k, X contient-il un sous-ensemble de taille k qui touche toutes les plages de R? La version paramétrée du problème est paramétrée par k.
Pour quelles valeurs de d est le problème d-Dimensional Hitting Set
- en FPT?
- dans W [1]?
- W [1] -hard?
- W [2] -hard?
Ce que je sais peut être résumé comme suit:
1-Dimensional Hitting Set est en P et donc en FPT. Si S a la dimension 1, il n’est pas difficile de démontrer qu’il existe un ensemble de frappes de taille 2 ou que la matrice d’incidence de S est totalement équilibrée. Dans les deux cas, nous pouvons trouver un jeu minimum de frappes en temps polynomial.
L'ensemble de frappe à 4 dimensions est W [1] -hard. Dom, Fellows et Rosamond [PDF] ont prouvé la dureté W [1] du problème de la perforation de rectangles parallèles aux axes dans R ^ 2 avec des lignes parallèles aux axes. Ceci peut être formulé en tant que jeu de frappe dans un espace de plage de VC-dimension 4.
Si aucune restriction n'est placée sur d, alors nous avons le problème standard de jeu de frappe qui est W [2] -complete et NP-complete.
Langerman et Morin [citeseer link] fournissent des algorithmes FPT pour Set Cover en dimension restreinte, bien que leur modèle de dimensionnalité lié ne soit pas identique à celui défini par la dimension VC liée. Leur modèle ne semble pas inclure, par exemple, le problème de frapper des demi-espaces avec des points, bien que le problème du prototype de leur modèle équivaut à frapper des hyperplans avec des points.
la source
Réponses:
Je pense que ce problème est trop difficile. Nous ne connaissons pas la réponse à des problèmes beaucoup plus faciles dans cette famille. Par exemple, étant donné un ensemble de n points dans le plan et un ensemble de (disons n) unités de disque, déterminez s’il existe une couverture des points par k des unités de disque. Il existe un algorithme simple n ^ O (k) time pour cela, et je ne serais pas surpris si vous utilisez des connaissances connues, vous pouvez faire n ^ O (sqrt {k}) (mais même cela n’est pas évident), mais f ( k) * n ^ {O (1)} est ouvert et serait en fait très intéressant. Une approximation (1 + eps) découle des travaux de Mustafa et Ray http://portal.acm.org/citation.cfm?id=1542362.1542367 .
BTW, pour la version continue où n’importe quel disque est permis, on peut résoudre le problème en n ^ {O (k)} temps. Dans ce cas, un PTAS est également assez facile à utiliser avec des grilles décalées.
la source
Nous abordons cette question dans une nouvelle pré-impression: http://arxiv.org/abs/1512.00481
Frapper Ensemble dans des hypergraphes de faible dimension VC (Karl Bringmann, László Kozma, Shay Moran, NS Narayanaswamy).
Il s'avère que Frapper Set est déjà dur [1] lorsque la dimension VC est égale à 2.
la source
Le document Dániel Marx: Schémas d’approximation efficaces pour des problèmes géométriques ?. SEC 2005: 448-459 est tout à fait pertinent.
la source