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

21

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 .jeN(X)
  • Sélectionnez une forme candidate avec le plus petit DIN ( ). Retirez-le et toutes les formes qu'il recoupe.argminXjeN(X)
  • Continuez jusqu'à ce qu'il ne reste plus de candidats.

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

entrez la description de l'image ici

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 nnn3n

entrez la description de l'image ici

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 kX1,...,XkjeN(X1,...,Xk)X1...XkmjenjeNk

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 , .mjenjeN1=3mjenjeN2=4kmjenjeNkk+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?mjenjeNkkmjenjeNkk

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.

Erel Segal-Halevi
la source
Il peut être intéressant de noter que le calcul du DIN peut être aussi difficile que le calcul d'un ensemble indépendant maximal lui-même. Par exemple, dans le cas de graphes de disques (plutôt que de graphiques de disques unitaires), on pourrait ajouter un grand disque coupant tous les autres objets de l'arrangement; le calcul de son DIN correspond au calcul d'un ensemble indépendant maximum dans l'arrangement d'origine.
Bart Jansen
2
@BartJansen Vrai, mais l'algorithme gourmand n'a en fait pas besoin de calculer le DIN pour chaque forme - il n'a besoin que d'une forme avec le DIN minimum. Étant donné que le DIN minimum est au maximum de 5 (dans le cas de disques de taille arbitraire), il suffit de vérifier tous les sous-ensembles avec au plus 6 disques et de voir si l'un d'eux est indépendant. Cela peut être fait dans le temps pour chaque forme. O(n6)
Erel Segal-Halevi
Pour votre dernière question - oui, c'est correct.
domotorp

Réponses:

19

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

C'est 3.entrez la description de l'image ici

Yury
la source
Il y a 32 disques unitaires ici, disposés en 2 niveaux de 16. Chaque disque intersecte 3 disques disjoints - 2 à son propre niveau et 1 à l'autre niveau. Mais, l'algorithme gourmand trouvera toujours une solution optimale, avec 16 disques.
Erel Segal-Halevi
Oui, cela ne répond qu'à 1/4 de la question :-)
Yury