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