Algorithmique 2 : Algorithmes d’approximation

Algorithmes d’approximation

Souvent :

Problème de décision NP-complet ⟺ Optimisation “difficile” (au moins aussi difficiles que les problèmes de décision)

Ex :

  • Problème d’optimisation : Couverture de sommets de taille la plus petite
  • Problème de décision : existe-t-il une couverture de sommets de taille $≤k$ ?
Algorithme en temps polynomial :

garantie de performance $𝛼>1$

\[C(sol) ≤ 𝛼 C^\ast\]

NB : en général, on cherche un minorant $K$ tq \(C(sol) ≤ 𝛼 K ≤ 𝛼 C^\ast\)

Schéma d’approximation polynomial pour un problème $Pb$ :

$𝜀>0$

\[𝒜(Pb, 𝜀) ⟶ C(sol) ≤ (1+𝜀) C^\ast\]
Schéma d’approximation totalement polynomial pour un problème $Pb$ :

$𝜀>0$

\[𝒜(Pb, 𝜀) ⟶ 𝒜(\vert Pb \vert, \frac{1}{𝜀})\]

Problèmes de décision NP-complets :

  • Existence d’un cycle hamiltionien non orienté

  • 3-coloring : Existence d’une coloration avec trois couleurs

  • Vertex-cover : existence d’une couverture de taille $k$

    • problème d’optimisation : trouver le $k$ min tel qu’il existe une couverture de taille $k$ ⟶ strictement plus dur ⟹ pas d’algo polynomial si P≠NP, intractable en pratique

$C>1$ : coefficient d’approximation tel qu’il existe une couverture de taille :

\[\vert couv \vert ≤ C \cdot \underbrace{k^\ast }_{k \text{ optimal}}\]

Problème :

  • on ne connaît pas $k^\ast$, mais on va pouvoir assurer l’inégalité précédente quand même.
Schéma d’approximation polynomial :

pour tout $𝜀>0$, $∃$ un algo $A_𝜀$ qui garantit $1+𝜀$

NB : croît plus que polynomialement en $𝜀$

Schéma d’approximation totalement polynomial (fully polynomial) :

pour tout $𝜀>0$, $∃$ un algo $A(G,𝜀)$ en $\vert G \vert, \frac{1}{𝜀}$

NB :

  • on veut un $C$ qui varie en fonction de la taille de l’instance

Couverture d’arêtes

Couverture d’arêtes : un sous-ensemble de sommets qui soit adjacent à toute arête.

NB : l’idée gloutonne qui consiste à prendre les sommets qui ont les plus grands degrés ne va pas permettre d’assurer la garantie de performance ⟶ il faut plus d’imagination.

$G ≝ (V, E)$

Couverture(V, E):
  Couv = set()
  F = E
  while F:
    Couv |= {u, v}
    F -= {arêtes adjacentes à u et v}
  return Couv

Temps linéaire + il y a un $C$ constant

\[C = 2\]
  • en effet : pour chaque $i$, toute couverture (donc en particulier la couverture optimale) contient $u_i$ OU $v_i$ (car les ensembles de sommets $\lbrace u_i, v_i \rbrace$ sont disjoints)

Voyageur de commerce

  • Ensemble de villes $\lbrace u_0, ⋯, u_{n-1} \rbrace$
  • Coût de transport : $c(u,v)≥0$

On cherche

\[\min_{𝛼∈𝕾_n} \left( \sum\limits_{ 0≤i≤n-1 } c(u_{𝛼(i)}, u_{𝛼(i+1 \mod n)}) \right)\]

Th : sauf si $P=NP$, il n’existe pas d’algorithme polynomial à garantie de performance constante

Preuve :

ABS : Supposons qu’il existe un algo $𝒜$ avec une garantie de performance $C$.

Soit $G ≝ (V, E)$ un graphe non orienté.

  • Villes = sommets
  • Si $\lbrace u, v \rbrace ∈ E$, on pose $c(u, v) ≝ 1$
  • Si $\lbrace u, v \rbrace ∉ E$, on pose $c(u, v) ≝ Cn+1$

(la réduction est dans LOGSPACE)

On fait tourner $𝒜$ :

  • Si il existe un cycle hamiltionien, l’algo renvoie une valeur $≤ Cn$
  • Si il n’existe pas de cycle hamiltionien, la solution optimale est $≥ Cn+1$ (puisque qu’on utilise frocément deux sommets non adjacents) donc $𝒜$ renvoie une valeur $>Cn$

CQFD.

NB : le coût, dans la preuve précédente, ne vérifie pas l’inégalité triangulaire.

⟶ Si $C$ est une distance :

  • on peut obtenir un rapport d’approximation $2$
  • beaucoup plus difficile : on peut obtenir un rapport d’approximation $3/2$

Et

  • si $C$ est une distance euclidienne, on peut montrer qu’il existe un schéma d’approximation polynomial.

Problème PCP

\[G = (V, E)\]

Arbre couvrant de poids minimal $T^\ast⊆E$

Parcours en profondeur de $T$ (on fait un parcours en profondeur, avec raccourcis lors des backtracks) : coût $≤ 2 × c(T^\ast) $

Cycle optimal (voyageur de commerce) : $𝒞^\ast$

$𝒞^\ast \backslash \lbrace 1 \text{ arête} \rbrace$ est un arbre couvrant

Donc

\[c(𝒞^\ast \backslash \lbrace 1 \text{ arête} \rbrace) ≥ c(T^\ast)\]

et

\[2 c(𝒞^\ast) ≥ 2 c(T^\ast)\]

Meilleur algo : rapport d’approximation $= 3/2$

Couplage :

on s’interdit de marier deux fois les mêmes personnes : un $M⊆E$ maximal (pour le cardinal) tq

\[∀ \lbrace u, v \rbrace, \lbrace u', v' \rbrace ∈ M, \lbrace u, v \rbrace ∩ \lbrace u', v' \rbrace = ∅\]

  • $G$ biparti : algo en temps polynomial

  • Ici : $G$ quelconque

Chemin $M$-augmentant :

chemin élémentaire (ne passe pas deux fois par le même sommet) dont les deux extrémités sont des arêtes n’appartenant pas au couplage $M$ et tel qu’il y a alternance arête de $M$/arête n’appartenant pas à $M$

NB : il n’est pas maximal, car si on prend les extrémités dans un nouveau $M’$ et qu’on alterne, $\vert M’ \vert = \vert M \vert +1$

$M$-fleur :

circuit élémentaire $v_0, v_1, ⋯ , v_{n-1}, v_n = v_0$ tel que $v_0∉M$ et il y a alternance arête dans $M$/pas dans $M$.

Clairement :

Il existe un chemin $M$-augmentant ⟹ $M$ non maximal

Montrons la réciproque :

Si il existe $M’$ un matching tel que $\vert M’ \vert > \vert M \vert$, on considère le graphe

\[H ≝ (V, M∪M')\]

dont toutes les arêtes sont dans $M$ ou $M’$

On remarque qu’il n’existe pas de sommet de degré supérieur à $3$ dans $H$ (car sinon, un des trois arêtes adjacentes n’appartient ni à $M$ ni à $M’$).

Comme $\vert M’ \vert > \vert M \vert$, il existe une composante connexe $𝒞$ tq

\[\vert 𝒞 ∩ M' \vert > \vert 𝒞 ∩ M \vert\]

Dans $𝒞$, il existe une arête $e∈M’ \backslash M$.

On construit le chemin alternant issu de $e$ (il alterne dans $M$/ dans $M’$)

Ce chemin ne peut pas être un cycle, car sinon $\vert 𝒞 ∩ M’ \vert ≤ \vert 𝒞 ∩ M \vert$

CQFD.

On s’intéresse à l’existence d’un chemin $M$-augmentant.

Problème du sac à dos

  • $\lbrace x_1, \ldots, x_n \rbrace, \; I = ⟦1,n⟧$
  • $t$

$J ⊆ I$

\[x_J ≝ \sum\limits_{ i∈J } x_i ≤ t\]

on cherche le $J$ qui réalise le max.

Liste ordonnée des paires (J, x_J) tq x_J ≤ t
L = (∅, 0)
for i in range(1,n+1):
  L0 = ∅
  for (J,x_J) in L0:
    if x_J + x_i ≤ t:
      L0 |= {J∪{i}, x_J + x_i}
  Fusionner(L,L0)
return L[-1]

Algo en temps exponentiel mais si $\vert L \vert$ est de taille polynomiale, alors l’algo est polynomial.

Facteur d’épuration $0<𝛿$ :

Liste ordonnée des paires (J, x_J) tq x_J ≤ t
L = (∅, 0)
for i in range(1,n+1):
  L0 = ∅
  for (J,x_J) in L0:
    if x_J + x_i ≤ t:
      L0 |= {J∪{i}, x_J + x_i}
  Fusionner(L,L0)
  Epurer(L)
return L[-1]

Si $(J^-, x_{J^-}), (J, x_J) ∈L$ et si

\[x_{J^-} ≤ x_J ≤ (1+𝛿) x_{J^-}\]

alors on supprime $(J, x_J)$

\[t ≥ x_i > (1+𝛿)^{i-1}\] \[t≥(1+𝛿)^{l-1} \\ ⟹ \log_{1+𝛿}(t) ≥ l-1 \\ ⟹ \vert L \vert ≤ 2 + \log_{1+𝛿}(t)\]
  • $x_{J_0}$ renvoyé par l’algo
  • $x_{J^\ast}$ la valeur optimale
\[x_{J_0}≥ \frac{x_{J^\ast}}{1+𝜀}\]

avec $𝜀≤1$

On va prendre

\[𝛿 ≥\frac{𝜀}{2n}\]

Soit $J ⊆ \lbrace 1, ⋯, k \rbrace$ et $x_{J} ≤ t$

Invariant de boucle :

$∃ \widehat{J} ∈L$ après la $k$-ième itération tel que

\[\frac{x_J}{(1+𝛿)^k} ≤ x_{\widehat{J}} ≤ x_J\]

$J ⟶ J^- = J \backslash \lbrace k \rbrace$

⟹ $∃ \widehat{J^-}∈L$ à la $k-1$-ème itération tq

\[\frac{x_{J^-}}{(1+𝛿)^{k-1}} ≤ x_{\widehat{J^-}} ≤ x_{J^-}\]

Donc

\[\frac{x_{J^-}+x_k}{(1+𝛿)^{k-1}} ≤ \frac{x_{J^-}}{(1+𝛿)^{k-1}} + x_k ≤ x_{\widehat{J^-}}+ x_k ≤ x_{J^-} + x_k\]

Leave a comment