Problème — La couverture par ensembles : un glouton qui perd un facteur logarithmique

1. Le glouton : prendre l'ensemble qui couvre le plus d'éléments encore découverts.

(* Nombre d'ensembles choisis par le glouton. Précondition : la réunion des
   familles couvre l'univers {0, ..., n-1}.
   Complexité : O(n m) avec des ensembles représentés par des listes. *)
let couverture n familles =
  let couvert = Array.make n false in
  let restants = ref n and pris = ref 0 in
  while !restants > 0 do
    let meilleur = ref (-1) and gain = ref 0 in
    List.iteri (fun i s ->
      let g = List.length (List.filter (fun x -> not couvert.(x)) s) in
      if g > !gain then begin gain := g; meilleur := i end) familles;
    List.iter (fun x -> if not couvert.(x) then begin
      couvert.(x) <- true; decr restants end) (List.nth familles !meilleur);
    incr pris
  done;
  !pris

Terminaison : variant restants, qui décroît strictement — tant qu'il reste des éléments découverts, le meilleur gain est $\ge 1$, puisque la réunion couvre $U$.

2. L'instance qui le piège. On prend $U$ de taille $n=2^{k+1}-2$, partitionné en $k$ blocs $C_1,\dots ,C_k$ avec $|C_i|=2^i$. On ajoute deux ensembles $A$ et $B$ qui partagent chaque bloc en deux moitiés égales : $|A|=|B|=2^k-1=n/2$.

L'optimum vaut $2$ : $A\cup B=U$.

Le glouton, lui, commence par $C_k$, de taille $2^k=n/2+1$, strictement plus grand que $A$ et que $B$. Puis $A$ et $B$ n'ont plus que $2^{k-1}-1$ éléments découverts chacun, tandis que $C_{k-1}$ en a $2^{k-1}$ : il prend $C_{k-1}$. Et ainsi de suite. Il prend les $k$ blocs.

Le rapport vaut $k/2\approx \frac{1}{2}{\log }_{2}n$ : il n'est borné par aucune constante.

3. La garantie logarithmique. Notons $\mathrm{OPT}$ la taille d'une couverture optimale, et $r_t$ le nombre d'éléments encore découverts après $t$ étapes du glouton, avec $r_0=n$.

Les $\mathrm{OPT}$ ensembles optimaux couvrent en particulier les $r_t$ éléments restants. L'un d'eux en couvre donc au moins $r_t/\mathrm{OPT}$. Comme le glouton choisit le meilleur de tous les ensembles, il en couvre au moins autant :

$$r_{t+1}\le r_t-\frac{r_t}{\mathrm{OPT}}=r_t(1-\frac{1}{\mathrm{OPT}}).$$

D'où $r_t\le n(1-1/\mathrm{OPT}{)}^t<n{e}^{-t/\mathrm{OPT}}$. Ce nombre devient $<1$ — donc nul, car entier — dès que $t>\mathrm{OPT}\ln n$. Le glouton s'arrête donc après au plus $\lceil \mathrm{OPT}\ln n\rceil$ étapes :

$$\mathrm{ALG}\le \mathrm{OPT}\ln n.$$

Une analyse plus fine, en comptant le coût imputé à chaque élément couvert, donne la borne exacte $\mathrm{ALG}\le H_n\cdot \mathrm{OPT}$.

Ce que ce problème apporte au chapitre. Il complète le tableau des trois régimes possibles pour un glouton :

Et le résultat est optimal en un sens fort : on démontre qu'aucun algorithme polynomial ne peut faire mieux que $(1-o(1))\ln n$ pour la couverture par ensembles, sauf si $\mathrm{P}=\mathrm{NP}$ (chapitre chap:decidabilite). Ce glouton simple est ce que l'on sait faire de mieux, et l'on sait aussi qu'on ne fera pas mieux.