Ensemble disjoint maximum: quel est le facteur d'approximation réel de l'algorithme gourmand?

Considérez le problème de la recherche d'un ensemble disjoint maximum - un ensemble maximum de formes géométriques qui ne se chevauchent pas, à partir d'une collection donnée de candidats. Il s'agit d'un problème NP-complet, mais dans de nombreux cas, l'algorithme gourmand suivant donne une approximation à facteur constant:

• Pour chaque forme candidate x , calculez son numéro d'intersection disjoint = le plus grand nombre de formes disjointes qui coupent x .$DIN(x)$
• Sélectionnez une forme candidate avec le plus petit DIN ( ). Retirez-le et toutes les formes qu'il recoupe.$\arg \min_{x} DIN(x)$
• Continuez jusqu'à ce qu'il ne reste plus de candidats.

Par exemple, considérez la figure suivante de la page Wikipedia:

Le disque vert coupe 5 autres disques, mais son DIN est de 3 (les 3 disques rouges sont disjoints). Les disques rouges les plus hauts et les plus bas coupent 2 autres disques, mais ils se coupent eux-mêmes, donc leur DIN est 1. Les disques jaunes ont un DIN de 2. L'algorithme gourmand sélectionne donc le disque rouge le plus haut ou le plus bas.

Si le DIN minimum peut être limité par une constante, alors l'algorithme gourmand est une approximation polynomiale à facteur constant.

Par exemple, si toutes les formes candidates sont des disques unitaires, Marathe et al (1995) montrent qu'un disque avec un DIN d'au plus 3 existe toujours: le disque le plus à gauche (le disque avec la plus petite coordonnée x) coupe au plus 3 autres disques disjoints . Par conséquent, l'algorithme gourmand donne une approximation à 3 car il obtient 1 disque pour chacun (au plus) 3 disques dans la solution optimale.

De même, si toutes les formes candidates sont des disques de taille arbitraire, l'algorithme gourmand donne une approximation de 5, car le plus petit disque recoupe au plus 5 autres disques disjoints, c'est-à-dire que le DIN minimum est au plus 5.

Jusqu'ici tout va bien, mais ces facteurs de 3 et 5 sont-ils serrés? Je ne suis pas sûr.

Considérez la figure ci-dessus. La sélection du disque le plus à gauche (vert) trouvera un ensemble disjoint de taille 1, qui est en effet une approximation de 3 du jeu disjoint maximum de taille 3 (rouge), mais, l'algorithme gourmand ne sélectionnera pas le disque vert - il sélectionnera le disque rouge haut / bas, dont le DIN est 1. Dans ce cas, l'algorithme gourmand trouvera la solution optimale.

Je n'ai pas pu trouver de contre-exemple pour le général , dans lequel l'algorithme gourmand trouve un ensemble disjoint avec disques unitaires tandis que l'ensemble disjoint maximum a . En fait, je ne pouvais même pas construire un contre-exemple général dans lequel le DIN minimum est en effet 3. Le meilleur que j'ai pu trouver est le suivant, dans lequel chaque disque d'unité croise au plus 2 autres disques disjoints (c'est-à-dire le DIN minimum est 2). Mais même ici, l'algorithme gourmand trouve la solution optimale plutôt qu'une approximation 2:n 3 $n$$n$$3n$

Mes questions sont:

• Quel est le DIN min max réel dans les collections de disques unitaires? Disques de taille arbitraire?
• Quel est le facteur d'approximation réel de l'algorithme gourmand pour les collections de disques unitaires? Pour les disques de taille arbitraire? (ce facteur est au plus aussi grand que le DIN min max, mais peut être plus petit).

MISE À JOUR: Pour chaque k-tuple de formes, , définissez = le plus grand nombre de formes disjointes intersectées par leur union . Définissez comme le DIN minimum de tous les k-tuples de formes disjointes. D I N ( x 1 , . . . , X k ) x 1 ∪ . . . ∪ x k m i n D I N $x_1,...,x_k$$DIN(x_1,...,x_k)$$x_1\cup...\cup x_k$$minDIN_k$

Par exemple, dans la réponse de Yury ci-dessous, , car chaque cercle intersecte 3 autres cercles. , car il est possible de sélectionner 2 cercles disjoints, l'un du cercle extérieur et l'autre du cercle intérieur, qui ne coupent ensemble que 4 autres cercles. Pour chaque , .$minDIN_1=3$$minDIN_2=4$$k$$minDIN_k\leq k+2$

JE PENSE que le rapport d'approximation de l'algorithme gourmand peut être limité par , car, pour chaque forme dans la solution optimale, nous avons au moins formes dans la sortie de l'algorithme. Est-ce correct?$\frac{minDIN_k}{k}$$minDIN_k$$k$

EDIT: Je suis en train de lire l'excellent livre Problèmes de recherche en géométrie discrète . Bien que je n'aie pas trouvé ce problème exact, j'ai trouvé un problème qui semble lié. Dans la section "2.5 Emballages minces avec de nombreux voisins", il existe des exemples d'emballages de cercles dans lesquels chaque cercle touche 5 autres cercles. Je me demande si un tel emballage peut donner une configuration de cercles avec DIN = 5.

Quel est le DIN minimal maximal réel dans les collections de disques unitaires?

C'est 3.