TD16 : Algorithmes d’approximation : Voyageur de commerce révisé, Bin packing

Énoncé

I. Voyageur de commerce révisé

1.

$G$ non orienté.

Supposons qu’il existe un cycle eulérien (qui passe par toutes les arêtes une fois et une seule) :

v_1 ⟶^{e_1} v_2 ⟶^{e_2} ⋯ ⟶{e_{k-1}} v_k ⟶^{e_k} v_1

Pour chaque sommet $v_i$, on a une arête qui “rentre” dans le noeud, et une arête qui “sort”.

Donc pour chaque noeud :

\deg (v) = \vert \lbrace e \mid e \text{ sort de } v \rbrace \vert + \vert \lbrace e \mid e \text{ rentre dans } v \rbrace \vert ∈ 2ℕ

Pour montrer l’autre direction : faisons une réc. sur le nombre d’arêtes $m$.

  • $m=1$ : Le graphe est de la forme

      graph {
        rankdir=TB;
        v -- v;    
      }
    

    ⟶ le résultat est acquis.

  • $m>1$ :

    • Cas 1 : il existe une noeud de la forme

      graph {
        rankdir=TB;
        v -- v[label="e"];    
      }
      

      Dans le graphe, on supprime $e$, on a un chemin eulérien et on peut donc conclure

    • Cas 2 : il existe deux noeuds de la forme

      graph {
        rankdir=LR;
        v -- u[label="e"];
        u -- v[label="e'"]   
      }
      

      On supprime $e$ et $e’$, et on obtient un ou deux graphes connexes où chaque noeud est de degré pair et on peut en utilisant HR reconstruire un chemin eulérien.

    • Cas 3 : il existe trois noeuds de la forme

      graph {
        rankdir=LR;
        v -- u[label="e"];
        u -- w[label="e'"]
        w -- v[style=dashed];
      }
      

      On supprime $e$ et $e’$, on ajoute l’arête en pointillés, et on obtient de nouveau un ou deux graphes connexes où chaque noeud est de degré pair et on peut en utilisant HR reconstruire un chemin eulérien (en remplaçant la nouvelle arête par $e, e’$)

2.

Montrer que pour tout graphe, le nombre de noeuds de degré impair est pair :

On regarde

\sum\limits_{ v∈V } \deg(v) = 2 \vert E \vert

modulo $2$.

3.

NB : Ici, le graphe est supposé complet.

  graph {
    1 -- 2 -- 3,4[penwidth=3]
    1 -- {3, 4};
    3 -- 4;
  }
G' = (V_p, V_p^2)

On veut montrer qu’il existe un ensemble $M⊆ V_p×V_p$ tq pour tout $(v_1, v_2), (v’_1, v’_2) ∈M$, $v_1 ≠v’_1$ et $v_2 ≠ v’_2$ (couplage) et tq pour tout $v∈V_p$, il existe $(v, v’)∈M$ (parfait).

C’est clair car $V_p$ est de cardinal pair et le graphe est complet : on prend $M ≝ \lbrace (v_{2i}, v_{2i+1}) \rbrace$.

4.

Soit $𝜋$ une solution au problème du voyageur de commerce

𝜋 ≝ v_1 𝜎_1 ⋯ v_k 𝜎_k

On transforme $𝜋$ en prenant les “raccourcis” entre les sommets de $V_p$ (on respecte l’inégalité triangulaire) :

𝜋 ≝ ⋯ v 𝜎 ⋯ v'𝜎' \quad \text{ où } v, v'∈V_p \\ ⟶ 𝜋' ≝ ⋯ v (vv') v'𝜎'

Donc

c(𝜋') ≤ c(𝜋)

On ne garde que les sommets de $V_p$ :

𝜋' ≝ v'_1 𝜎'_1 ⋯ v'_{2m} 𝜎'_{2m} v'_1

avec $V_p ≝ \lbrace v’1, \ldots, v’{2m} \rbrace$

Mq

c(M) ≤ c(𝜋')/2

Prenons $N_1 ≝ \lbrace 𝜎’1, ⋯, 𝜎’{2m-1} \rbrace, N_2 ≝ \lbrace 𝜎’2, ⋯, 𝜎’{2m} \rbrace$

$N_1$ et $N_2$ sont des couplages parfaits de $G’$ :

c(M) ≤ \min (c(N_1), c(N_2)) ≤ \frac{c(N_1)+c(N_2)}{2} ≤ c(𝜋')/2

Récapitulons :

  1. On construit un arbre couvrant de poids minimal $T$, dans lequel on marque tous les sommets de degré impair $V_p$.

  2. on trouve un couplage parfait $M$ sur $V_p$

  3. en ajoutant aux arêtes de $T$ les arêtes de $M$, on obtient un graphe dont tous les sommets sont de degré pair.

  4. Il existe donc, dans ce graphe, un chemin eulérien $ch$, qui vérifie donc :

c(ch) = c(T) + c(M) ≤ \underbrace{c(𝜋^\ast)}_{\rlap{\text{car en enlevant une arête, on a un arbre, non forcément minimal}}} + c(𝜋^\ast)/2 = 3/2 c(𝜋^\ast)
  1. A partir de $ch$, on construit un chemin Hamiltonien $ch’$ en “court-circuitant” les sommets déjà rencontrés.

  2. Par l’inégalité triangulaire :

c(ch') ≤ c(ch) ≤ 3/2 c(𝜋^\ast)

II. Bin-packing

On se donne des rationnels $x_1, ⋯, x_n$, avec $x_i ≤ 1$ pour tout $i$.

Trouver le plus petit ensemble de paquets où mettre les $x_i$ sachant que dans chaque paquet, la somme des $x_i$ doit être inférieure à $1$.

On cherche un $m$ minimal, $f:⟦1,n⟧ ⟶ ⟦1,m⟧$ tq pour tout $b∈⟦1, m⟧$ :

\sum\limits_{ i∈f^{-1}(b) } x_i ≤ 1

1. Algo glouton

A chaque étape :

On dispose de $i$ paquets : on place le $x_k$ dans le premier paquet qui peut l’accueillir.

Mq il existe $m-1$ paquets dont la capacité est strictement supérieure à $1/2$.

Soit $m_i$ le nombre de paquets quand on a mis $x_1, ⋯, x_i$ et $m’_i$ remplis à la moins de la moitié.

On veut montrer l’invariant

$m’_i ≤ 1$ à la fin de l’étape $i$.

Induction sur $i$ :

  • $i=1$ : évident.

  • $i>1$ :

    • si $m’_{i-1} = 0$ au début de l’étape $i$, le résultat est acquis (car nécessairement $m’_i ≤ 1$ à la fin)

    • si $m’_{i-1} = 1$ au début de l’étape $i$ : alors on ne peut ajouter un paquet QUE SI $x_i> 1/2$ (car sinon $x_i$ est mis dans le paquet rempli à moins de la moitié). Mais dans ce cas, le nouveau paquet ajouté contenant $x_i$ n’est pas rempli à moins de la moitié, et on a toujours $m’_i = 1$

2.

Il y au moins un $x_i$ dans chaque paquet, et chauque $x_i$ est dans un paquet, donc

S = \sum\limits_{ i } x_i ≤ m

3.

Soit $m^\ast$ une solution optimale, on veut montrer que

m ≤ 2 m^\ast

Comme $S ≤ m^\ast$, il suffit de montrer que $m ≤ 2S$ : par la question 1,

S = \sum\limits_{ i } x_i > \frac{m-1}{2} \\ 2 S > m-1

le résultat est acquis.

Exercice 3

Exemple où l’algo de l’exo 3 est meilleur que l’algo de l’exo 1 :

x_1, ⋯, x_n = 1/2,\; 1/m,\; 1/2,\; 1/m,\; ⋯

OU encore :

$0,7 - 0,2 - 0,6 - 0,3 - 0,2$


Comme $x_i> 1/2$ et comme

x_1 ≥ x_2 ≥ ⋯ ≥ x_i

il n’existe pas de solution où deux des $\lbrace x_1, ⋯, x_b \rbrace$ partagent un même paquet.

Donc

m^\ast ≥ b

3.

a).

Tous les éléments $b’∈⟦b, m-1⟧$ ne contiennent que des éléments inférieurs ou égaux à $1/2$.

Donc il y a au moins 2 éléments dans chacun de ces paquets, ce qui donne un total de $2(m-b)$ éléments.

b).

1er Cas : $b ≤ 2(m-b)$

Les $b-1$ premiers paquets ont un poids strictement inférieur à $2(m-b)$, donc pour chaque paquet de $\lbrace 1, ⋯, b-1 \rbrace$, on prend des un des $2(m-b)$ éléments contenus dans les paquets $\lbrace b, ⋯, m-1 \rbrace$ et on l’ajoute au paquet, lui faisant dépasser sa capacité.

On en déduit que $S>b-1$.

b).

2eme Cas : $b > 2(m-b)$

Même technique mais on ne peut en remplir que $2(m-b)$ donc $S> 2(m-b)$.

4.

Cas limite : $b= \frac{2m}{3}$

Dans le premier cas :

S > b-1 = 2/3 m - 1 \\ ⟹ m^\ast ≥ 2/3 m \\ ⟹ m ≤ 3/2 m^\ast

Dans le deuxième cas :

m^\ast ≥ S > 2(m - \frac 2 3 m) = 2/3 m \\ ⟹ m ≤ 3/2 m^\ast

Problème PARTITION :

  • Input : $A ≝ \lbrace a_1, ⋯, a_n \rbrace$ un multi-ensemble

  • Output : $∃I⊆ \lbrace 1, ⋯, n \rbrace$ tq

    \sum\limits_{ i∈I } a_i = \sum\limits_{ i∈⟦1,n⟧ \backslash I } a_i

1.

C’est clair, car le bloc contenant $a_i$ aura un poids strictement plus grand que l’autre.

2.

On réduit PARTITION à BIN-PACKING.

On pose

x_i ≝ \frac{2a_i}{\sum\limits_{ i } a_i}

Supposons qu’il y ait une solution de BIN-PACKING de taille 2 :

En notant $\lbrace x_1, ⋯, x_k \rbrace$ (resp. $\lbrace x_{k+1}, ⋯, x_n \rbrace$) le premier (resp. le deuxième) paquet :

On a nécessairement :

\sum\limits_{ i ≤ k } x_i = \sum\limits_{ k < i ≤ n } x_i = 1

car sinon, si $\sum\limits_{ i ≤ k } x_i < 1$, il vient que $\frac{2 \sum\limits_{ i } x_i }{\sum\limits_{ j } x_j} = \sum\limits_{ i ≤ n } x_i < 2$ : absurde.

Donc on a une solution à PARTITION.

Le cas PARTITION ⟶ BIN-PACKING de taille 2 est identique.

3.

Si $k<3/2$.

Soit $m$ la solution donnée par l’algorithme d’approximation sur BIN-PACKING déduit de partition :

m < 3/2 m^\ast

S’il y a une partition, on a $m^\ast=2$, et donc $m=2$ car $m<3/2 m^\ast = 3$.

S’il n’y a pas de partition, on a $m> 2$ et et $m≥m^\ast> 2$

Donc si $k≤ 3/2$, l’algorithme polynomial résout un problème NP-complet, impossible si $P≠NP$.

Exercice 5.

Soit $𝜀>0$ et $d∈ℕ$.

On suppose que l’on a que $d$ valeurs toutes supérieures à $𝜀$.

On peut borner le nombre d’éléments dans un paquet :

L = \lfloor 1/𝜀 \rfloor

Nombre de suites de $d$ entiers dont la somme vaut $L$ :

M ≝ \binom{L+d-1}{L}

Le nombre de paquets est au plus $n$ (nombre de valeurs que l’on a) :

Donc le nombre de possibilités est

\binom{n+M-1}{n} = c n^M

⟶ le nombre de solutions possibles est polynomial (à $d$ et $𝜀$ fixés).

2.

m^\ast(H) ≤ m^\ast(I) ≤ m^\ast(J)

car une solution pour $I$ est une solution pour $H$, et une solution pour $J$ est une solution pour $I$.

Mq

m^\ast(J) ≤ m^\ast(H)+Q ≤ m^\ast(I)+Q

Si on choisit $P$ tq $Q ≤ 𝜀 m^\ast(I)$ :

m^\ast(J) ≤ m^\ast(I)(1+𝜀)

Leave a Comment