Algorithmes d'approximation pour les problèmes d'affectation multidimensionnels

Le problème d'affectation multidimensionnel (PAM) consiste à partitionner les sommets
d'un graphe m-parti en m-cliques disjointes de façon à minimiser la somme des coûts
des cliques utilisées, où le coût des cliques peut être défini de différentes façons.
PAM généralise le problème d'affectation ou de couplage biparti classique qui
correspond au cas m=2.
Nous présentons plusieurs résultats, anciens et nouveaux, relatifs à des cas particuliers
de PAM obtenus en spécifiant les propriétés du coût des cliques. Pour ces cas particuliers,
nous décrivons des algorithmes d'approximation, nous examinons leurs garanties de
performance, et nous mentionnons quelques questions ouvertes.