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...
Considérez le problème de couverture de l'ensemble minimal avec les restrictions suivantes: chaque ensemble contient au plus éléments et chaque élément de l'univers se produit dans au plus ensembles.kkkfff Exemple: le cas et est équivalent au problème de couverture minimale des sommets dans les...
Est-il possible de tester algorithmiquement si un nombre calculable est rationnel ou entier? En d'autres termes, serait-il possible pour une bibliothèque qui implémente des nombres calculables de fournir les fonctions isIntegerou isRational? Je suppose que ce n'est pas possible, et que cela est en...
Étant donné un ensemble S de matrices de permutation nxn (qui n'est qu'une petite fraction des n! Matrices de permutation possibles), comment pouvons-nous trouver des sous-ensembles de taille minimale T de S tels que l'ajout des matrices de T a au moins 1 dans chaque position? Je suis intéressé par...
Quelle est la variation suivante sur la couverture de l'ensemble appelée? Etant donné un ensemble S, une collection C de sous-ensembles de S et un entier positif K, existe-t-il K ensembles en C tels que chaque paire d'éléments de S se trouve dans l'un des sous-ensembles sélectionnés. Remarque: Il...
Considérons une collection d'ensembles F = { F 1 , F 2 , … , F n } sur un ensemble de base U = { e 1 , e 2 , … , e n } où | F i | ≪ n et e i ∈ F i , et soit k un entier positif.F= { F1, F2, … , Fn}F=\{F_1,F_2,\dotsc,F_n\}U= { e1, e2, … , En}U=\{e_1,e_2,\dotsc,e_n\}| Fje||F_i| ≪\ll nneje∈ Fjee_i \in...
L' entrée est un univers et une famille de sous - ensembles de U , par exemple, F ⊆ 2 U . Nous supposons que les sous - ensembles de F peuvent couvrir U , c. -à- ⋃ E ∈ F E = U .UUUUUUF⊆ 2UF⊆2U{\cal F} \subseteq 2^UFF{\cal F}UUU⋃E∈ FE= U⋃E∈FE=U\bigcup_{E\in {\cal F}}E=U Une séquence de recouvrement...
Ainsi, le problème de couverture d'ensemble est trivial si aucun des ensembles candidats ne se recoupe. Cependant, que faire si la taille de l'intersection pour une paire d'ensembles candidats était au plus 1? Ce problème est-il difficile à résoudre? J'apprécierais toute idée. Merci,...
Beaucoup ici sont probablement au courant de la baisse super-linéaire limite récente pour Alon -nets dans un cadre géométrique naturel [PDF] . Je voudrais savoir ce que, le cas échéant, une telle borne inférieure implique au sujet de l'approximation des problèmes de jeu de couverture / jeu de...
Supposons que j'ai un polygone simple et un entier k . Quelles sont les approches existantes pour trouver le plus petit rayon r tel que je puisse couvrir S avec k cercles de rayon r ? Que diriez-vous si r est fixe, et je veux minimiser k
Quelle est la difficulté du problème Set Cover si le nombre d'éléments est limité par une fonction (par exemple, lognlogn\log n ) où nnn est la taille de l'instance de problème. Officiellement, Soit U={e1,⋯,em}U={e1,⋯,em}\mathcal{U}=\{e_1, \cdots, e_m\} et où et . Est-il difficile de décider du...
J'essaie de montrer qu'un certain problème est inapproximable par une réduction de la couverture réglée. Ma réduction transforme une instance avec un ensemble au sol de taille et ensembles en une instance de mon problème où un certain paramètre est de taille . Je peux alors montrer qu'une instance...