La 2-approximation est-elle serrée ? et le glouton « degré maximal » a-t-il une garantie ?

Le rapport $2$ est atteint, et sur des graphes triviaux. Mesuré :

Sur un couplage parfait, l'algorithme prend tous les sommets alors que la moitié suffit : le facteur $2$ est donc serré, on ne peut pas améliorer la garantie sans changer d'algorithme.

Et le glouton par degré maximal ? Il gagne sur tous ces petits cas — et c'est exactement ce qui le rend dangereux. Il n'a aucune garantie constante. Sur la famille d'instances bipartites classique — $k$ sommets à gauche, et pour chaque $i$ de $2$ à $k$ un groupe de $\lfloor k/i\rfloor$ sommets à droite reliés chacun à $i$ sommets de gauche —, le côté gauche est une couverture, et c'est la plus petite : le graphe étant biparti, le théorème de König donne $\mathrm{OPT}=$ taille d'un couplage maximum, calculée exactement ici par chemins augmentants (chapitre chap:graphes-avances), et l'on trouve $\mathrm{OPT}=k$.

À $k=32$, le glouton « intelligent » prend $87$ sommets là où $32$ suffisent : il dépasse largement le facteur $2$, tandis que le glouton « stupide » par couplage reste à $62\le 2\times 32$, comme sa démonstration l'y oblige. On établit que le rapport de cette famille croît comme $H_k={\sum }_{i\le k}1/i\sim \ln k$ : il n'est borné par aucune constante, et la colonne le montre déjà.

Ce que cette comparaison enseigne, et c'est le cœur du chapitre. Le glouton par degré maximal est meilleur en pratique sur presque toutes les instances, et il n'a aucune garantie. Le glouton par couplage est souvent moins bon, et il a une garantie prouvée. Ce sont deux qualités différentes, et l'une ne s'achète pas avec l'autre.

Le cours le disait déjà : « un glouton d'approximation aussi se démontre ; sans preuve, on ignore s'il vaut $2$ ou $n$ ». On vient de voir un cas où l'intuition dit $2$ et où la vérité est $\ln k$.