Le glouton est une 2-approximation, et pas mieux

La preuve. Soit $e=\{u,v\}$ une arête de $M^{\ast }$. Comme $M$ est maximal, on n'a pas pu ajouter $e$ à $M$ : c'est donc qu'au moins l'une de ses deux extrémités est déjà saturée par $M$. Associons à $e$ une telle extrémité.

Cette application, de $M^{\ast }$ vers les sommets saturés par $M$, est au plus 2 pour 1 : deux arêtes de $M^{\ast }$ ne partagent aucune extrémité, donc deux arêtes distinctes de $M^{\ast }$ reçoivent des sommets distincts. Or les sommets saturés par $M$ sont exactement les $2|M|$ extrémités des arêtes de $M$. Donc

$$|M^{\ast }|\le 2|M|,\text{c’est-aˋ-dire}|M|\ge \frac{1}{2}|M^{\ast }|.$$

La borne est atteinte, et l'exemple est celui du chapitre : le chemin $u_1{v}_1$, $u_1{v}_2$, $u_2{v}_2$. Si le glouton examine $u_1{v}_2$ en premier, il la prend et rien d'autre n'est possible : $|M|=1$ alors que $|M^{\ast }|=2$. Le rapport vaut exactement $1/2$.

La mesure. Sur $18772$ graphes bipartis aléatoires (jusqu'à $5+5$ sommets), le rapport glouton/maximum le plus bas observé vaut $0,500$ — jamais moins, conformément à la preuve — et le glouton atteint le maximum dans $16892$ cas, soit $90\%$. L'heuristique est presque toujours optimale, et sa garantie est deux fois plus faible : c'est précisément l'écart entre le comportement moyen et le pire cas.

Le rapprochement à faire. Ce raisonnement est celui de la 2-approximation de la couverture des sommets du chapitre chap:gloutons, retourné : là-bas on majorait le coût de l'algorithme par $2|M|$ en minorant l'optimum par $|M|$ ; ici on majore l'optimum par $2|M|$. C'est le même couplage maximal qui sert de pivot dans les deux sens. Le chapitre chap:probabilistes en fera la structure générale de toute preuve d'approximation.