PA Info et autres Promotion 2012

INF550. Algorithmique avancée

Examen du mercredi 3 décembre 2014. 3 heures
Documents autorisés : transparents et notes de cours,
énoncés et corrigés de PC

On vous demande d’accorder une attention particulière à une rédaction soignée, qui sera un critère important
dans l’évaluation. Les différents exercices sont indépendants et peuvent être traités dans l’ordre de votre choix. Il
n’est pas nécessaire de toucher à tous les exercices pour avoir une bonne note.

Compétitivité de la politique du vide (Algorithmes online)

On considère le problème de la gestion d’un cache mémoire de capacité k pages, dans le modèle avec
coût unitaire pour les chargements de pages et coût nul pour la consultation des pages dans le cache. La
politique de gestion FlushAll consiste à vider le cache à chaque fois qu’il est plein : plus précisément,
on vide le cache lorsqu’il contient k pages et qu’arrive une requête à une page qui n’est pas dans le cache.
Cet algorithme est il α-compétitif ? Si oui pour quel α ?

Circulations et arrondi de matrices (Flots)

On considère un graphe orienté G = (V, E) avec une capacité c(e) > 0 sur chaque arc e ∈ E, et
une ressource ou demande d(v) ∈ R sur chaque sommet v ∈ V : si d(v) > 0 le sommet v est appelé un
fournisseur, si d < 0 c’est un client, et si d = 0 c’est un nœud de transit.
Une circulation sur le réseau (G, d, c) est une fonction f : E → R≥0 satisfaisant aux deux conditions
suivantes :
– Contrainte de capacité : pour tout arc e ∈ E, 0 ≤ f (e) ≤ c(e).
– Conservation du flot : pourP tout sommet P v ∈ V , la somme des flots sortants moins la somme des
flots entrants vaut d(v) : e=vu f (e) − e=uv f (e) = d(v).
1. Donner une condition nécessaire portant sur la fonction d pour l’existence d’une circulation sur
(G, d, c).
2. Montrer par la réduction à un problème de flot maximum qu’on peut décider de l’existence d’une
circulation en temps polynomial. Quelle est la complexité de votre algorithme ?
3. Montrer qu’une et une seule des deux conditions suivantes est satisfaite :
(a) Il existe une circulation dans le réseau (G, d, c)
(b) Il existe une partition (A, B) de V telle que la somme des demandes des clients de B est
strictement supérieure en valeur absolue à la somme des ressources des fournisseurs de B plus
la somme des capacités des arcs de A vers B.
On ajoute maintenant des contraintes supplémentaires en imposant pour chaque arc e ∈ E une borne
inférieure `(e) sur le flot qui l’emprunte dans la circulation. Plus précisément, une circulation avec bornes
inférieures dans (G, d, c, `) est une circulation f dans (G, d, c) telle que f (e) ≥ `(e) pour tout arc e de G.
4. Construire un réseau (G, d00 , c00 ) tel qu’il existe une circulation avec bornes inférieures dans (G, d, c, `)
si et seulement si il existe une circulation dans (G, d00 , c00 ). Indication : on pourra se demander
comment modéliser la contrainte f (e) ≥ `(e) pour e = uv en modifiant localement d(u), d(v) et
c(e).

1
 5. Montrer que si les capacités c(e), les bornes inférieures `(e) et les ressources/demandes d(v) sont à
valeurs entières et qu’il existe une circulation avec borne inférieure dans (G, d, c, `), alors il existe
une circulation avec borne inférieure à valeurs entières dans (G, d, c, `).
Soit D = (di,j ) une matrice de taille p × q de nombres réels. On note ai la somme des entrées de la
ième rangée de D et bj celle des entrées de la jème colonne. On veut arrondir chaque di,j à l’entier au
dessus ou en dessous de sorte que la somme des éléments arrondis de chaque ligne ou colonne soit égale
à l’arrondi de l’entrée ai ou bj correspondante : plus précisément on veut choisir des sens d’arrondis εi,j ,
αi et βj dans {0, 1} tels que pour tout i et tout j,
q
X
(bdi,j c + εi,j ) = bai c + αi
j=1

et
p
X
(bdi,j c + εi,j ) = bbj c + βj .
i=1

6. Appliquer le résultat de la question précédente à un reseau de p + q + 2 sommets bien choisi pour

montrer qu’il existe toujours un arrondi faisable.

Optimisation de tests (Programmation linéaire, algorithme d’approximation)

On considère un ensemble P de n propriétés, qu’on numérote de 1 à n (autrement dit, P = {1, . . . , n}).

Un test faisable est un sous-ensemble de propriétés P qu’il est possible de tester en parallèle : un test
faisable T ⊂ P permet de savoir en une seule fois lesquelles des propriétés de T sont satisfaites. Chaque
test a un coût w(T ) > 0. Soit T l’ensemble des tests faisables. On appelle m = |T | le nombre de tests
faisables et f = maxi∈P |{T ⊂ T | i ∈ T }|. S
On suppose que toutes les propriétés peuvent être testées : T ∈T T = P . Le problème d’optimisation
des tests est de trouver un sous-ensemble
P R ⊂ T de coût minimal permettant de tester toutes les
propriétés : le coût de R est w(R) = T ∈R w(T ) et on cherche
( )
[
min w(R) R ⊂ T , =P .
T ∈R

1. Modéliser ce problème par un problème de programmation linéaire portant sur m variables (xT )T ∈T
à valeur dans {0, 1}.
2. On considère la relaxation du programme linéaire L de la question précédente où on remplace les
conditions xT ∈ {0, 1} pour T ∈ T par

xT ≥ 0 pour T ∈ T .

Montrer que le coût W opt de l’optimum (xopt 0

T )T ∈T de ce nouveau programme linéaire L est inférieur
opt opt
au coût C du meilleur ensemble de tests et que xT ≤ 1 pour tout T ∈ T .
3. Étant donnée la solution optimale (xopt 0 0
T )T ∈T du programme linéaire L on pose R = {T ∈ T |
opt
xT ≥ 1/f }, où on rappelle que f = maxi∈P |{T ⊂ T | i ∈ T }|. Montrer que l’ensemble de tests R0
permet de tester toutes les propriétés.
4. Montrer que le choix de R0 défini à la question précédente est une f -approximation de la solution
optimale au problème d’optimisation des tests.
5. Écrire le programme linéaire dual L∗ de L0 . On notera (yi )i∈P les variables de ce programme.

2
 6. Montrer que pour toute solution faisable y du programme dual,
X
yi ≤ C opt
i∈P

7. On considère une solution optimale y opt

du programme dual. Montrer que l’ensemble R00 ⊂ T des
tests T pour lesquels X
yiopt = w(T )
i∈T
est un ensemble de tests qui permet de tester toutes les propriétés et que son coût est inférieur à
f · C opt .
8. On considère maintenant l’algorithme suivant (appelé algorithme primal-dual ) :
– y ← 0, R ← ∅ S
– tant qu’il existe i ∈
/ T ∈R T faire
– Augmenter yi jusqu’à ce qu’il existe un T tel que
X
yj = w(T ).
j∈T

– Ajouter T à R : R ← R ∪ {T }.
Montrer que cet algorithme donne une solution f -approchée au problème du test optimal sans avoir
besoin de résoudre les programmes linéaires associés.

Indépendant maximum dans les graphes planaires (Algorithme paramétrique,

largeur arborescente, approximation)
Un graphe plan G = (G, φ) est un graphe connexe G muni d’un dessin φ : G → P dans le plan P sans
croisement d’arêtes. Une face de G est une composante connexe de P \ φ(G). La face extérieure de G est
l’unique face de G qui s’étend à l’infini.
La profondeur (ou profondeur d’oignon) d’un graphe plan est le nombre de couches de sommets
extérieurs qu’il faut supprimer pour le détruire entièrement. Plus formellement :
– Un graphe plan est de profondeur 0 si tous ses sommets sont incidents à la face extérieure.
– Un graphe plan G est de profondeur ≤ i + 1 si tous les G0j ont profondeur inférieure ou égale à i,
où les G01 , . . . , G0k sont les composantes connexes du graphe G0 obtenu en supprimant les sommets
de G incidents à la face extérieure et toutes les arêtes qui leur sont incidentes.
Autrement dit on définit la profondeur i d’un sommet de G comme le nombre d’épluchages des sommets
de la face extérieure nécessaires pour l’amener sur la face extérieure : la profondeur de G est alors le
maximum des profondeurs des sommets de G. On admet le résultat combinatoire suivant :
– Tout graphe plan à n sommets de profondeur i admet une décomposition arborescente de largeur
arborescente 3i + 1 et de taille 2n, et on peut la calculer en temps O(2O(i) n2 )
On rappelle que le problème Indépendant maximum est de déterminer, étant donné un graphe G
et un entier ` ≥ 0, s’il existe ` sommets de G qui ne sont pas voisins deux à deux.
1. Montrer qu’il existe un algorithme de complexité O(2O(i) n2 ) pour résoudre Indépendant maxi-
mum sur un graphe plan de profondeur i.
Étant donné un graphe G et un entier k ≥ 2 on considère les graphes Gi = G \ Vi où Vi est l’ensemble
des sommets de G de profondeur i modulo k, pour i = 0, . . . , k − 1. En particulier G0 contient les
sommets de profondeur 1, 2, . . . , k −1, k +1, . . . , 2k −1, 2k +1, . . . alors que G1 contient ceux de profondeur
0, 2, 3, . . . , k, k + 2, . . .
2. Montrer que chaque composante connexe du graphe Gi a profondeur au plus k.
3. Déduire de la question précédente une façon de trouver en temps O(2O(k) n2 ) un ensemble indépendant
de taille au moins (1 − k1 )|I ∗ | où I ∗ est un indépendant maximum de G.
4. Déduire de la question précédente un schéma d’approximation polynomial pour le problème de
l’indépendant maximal qui donne une solution ε-approchée en temps O(2O(1/ε) n2 ).