Une parade qui vaut 2, et pourquoi elle vaut 2

L'algorithme, avec le glouton du cours écrit au complet :

(* Valeur du glouton par rapport valeur/poids décroissant, objets ENTIERS.
   Précondition : p.(i) > 0. Complexité : Theta(n log n). *)
let sac_glouton p v c =
  let n = Array.length p in
  let idx = Array.init n (fun i -> i) in
  Array.sort (fun i j ->
    compare (float_of_int v.(j) /. float_of_int p.(j))
            (float_of_int v.(i) /. float_of_int p.(i))) idx;
  let reste = ref c and total = ref 0 in
  Array.iter (fun i ->
    if p.(i) <= !reste then begin
      reste := !reste - p.(i); total := !total + v.(i) end) idx;
  !total

(* Renvoie au moins la moitié de l'optimum du sac à dos entier.
   Précondition : p.(i) > 0 et v.(i) >= 0. Complexité : Theta(n log n). *)
let sac_parade p v c =
  let n = Array.length p in
  let seul = ref 0 in
  for i = 0 to n - 1 do
    if p.(i) <= c && v.(i) > !seul then seul := v.(i) done;
  max (sac_glouton p v c) !seul

La démonstration. Rangeons les objets par rapport $v_i/p_i$ décroissant, et notons $k$ l'indice du premier objet que le glouton ne peut plus mettre — le premier « refusé ». Notons $G$ la valeur des objets $0,\dots ,k-1$, tous pris, et $F$ l'optimum fractionnaire.

Le glouton fractionnaire prend les objets $0,\dots ,k-1$ entièrement, puis une fraction de l'objet $k$. Donc

$$F\le G+v_k.$$

Or l'optimum entier $\mathrm{OPT}$ vérifie $\mathrm{OPT}\le F$ (exercice précédent). D'où $\mathrm{OPT}\le G+v_k$, et par conséquent

$$\max (G,v_k)\ge \frac{G+v_k}{2}\ge \frac{\mathrm{OPT}}{2}.$$

La solution gloutonne vaut au moins $G$, et le meilleur objet seul vaut au moins $v_k$ — car $v_k$ tient dans le sac, $p_k\le C$. Le maximum des deux vaut donc au moins $\mathrm{OPT}/2$. C'est une $2$-approximation.

La vérification. Sur $200000$ instances tirées au hasard ($2$ à $5$ objets, poids $\le 20$, valeurs $\le 40$, capacité $\le 35$), l'optimum a été calculé par table et comparé aux deux algorithmes :

Le pire rapport de la parade reste sous $2$, comme la preuve l'exige. Et la famille du cours — un objet $(p=1,v=2)$ et un objet $(p=C,v=C)$ — donne pour le glouton seul :

Le rapport du glouton seul vaut $C/2$ : arbitrairement mauvais, exactement comme le cours l'annonce. La parade, elle, est exacte sur cette famille.

Ce qu'il faut retenir de la structure de la preuve. On n'a jamais comparé l'algorithme à l'optimum — qu'on ne sait pas calculer. On l'a comparé à une majoration de l'optimum, l'optimum fractionnaire, qui, elle, se calcule. C'est le patron de toute preuve d'approximation, et il est le même que pour la couverture des sommets : là on minorait $\mathrm{OPT}$ par la taille d'un couplage, ici on le majore par le fractionnaire. Minimisation : minorer l'optimum. Maximisation : le majorer.