Devoir en temps libre d’algorithmique à rendre le lundi 26 novembre 2001

à Natacha Portier

À rédiger soigneusement.

Partition

La crémière donne à Jean-Claude et Pascal un plateau de fromages. Ils se répartissent les morceaux, sans les couper, et tout en cherchant à avoir autant que possible le même poids de fromage chacun.

Une donnée du problème de partition est un ensemble fini X = {x_{1}, …, x_{n}} d’objets, avec pour chaque objet son poids a_{i} ∈ ℕ. On supposera (quitte à commencer par un tri si nécessaire) que les objets sont triés par poids décroissant.

Une solution est un couple S = (Y_{1}, Y_{2}) d’ensembles disjoints tels que X = Y_{1} ∪ Y_{2}. La mesure de cette solution est max(∑_{x_{i}∈Y_{1}} a_{i}, ∑_{x_{i}∈Y_{2}} a_{i}). On cherche à trouver une solution de mesure aussi petite que possible. On notera m^{∗} la mesure d’une solution optimale.

Q1 Quel est le rapport entre le plateau de fromage et le problème de partition ? Montrez qu’il existe une constante K telle que m(S) ≤ Km^{∗} pour toute donnée et toute solution S.

Q2 Donner l’algorithme glouton pour ce problème. Pour quelles valeurs de n

est-il optimal ? Q3 Pour r ∈]1, 2[ on pose k(r) = ⌈(2−r)/(r−1)⌉. On supposera que n ≥ k(r).

On étudie un nouvel algorithme qui fonctionne en deux phases :

1. Construire par recherche exhaustive une solution optimale du problème restreint aux objets {x_{1}, …, x_{k(r)}} (qui sont par hypothèse les k(r) plus lourds objets).

2. On complète la solution obtenue pour obtenir une solution du pro-

blème de départ en utilisant l’algorithme glouton. Evaluer la complexité de cet algorithme.

Q4 Soit Y_{i} l’ensemble le plus lourd à la fin de l’algorithme. Montrez que si aucun objet n’est ajouté à Y_{i} durant la deuxième phase alors la solution produite est optimale.

Q5 Montrez que dans le cas contraire la solution S produite par l’algorithme

vérifie m(S) ≤ rm^{∗}. Q6 Montrez que la mesure de la solution produite par l’algorithme glouton

vérifie toujours m_{g} ≤ 6m^{∗}/5.