Fonction sous-modulaire

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

Les fonctions sous-modulaires jouent un rôle important en optimisation combinatoire.

Dans ce contexte il s'agit de sous-modularité sur des fonctions d'ensemble, c'est-à-dire des fonctions de l'ensemble des parties d'un ensemble (que l'on peut supposer fini) dans l'ensemble des réels. (Le terme « sous-modulaire » s'applique aussi pour les fonctions continues.)

Donc, soient E un ensemble et f une fonction qui à tout sous-ensemble X de E associe un réel f(X), on dit que f est sous-modulaire si l'inégalité suivante est vérifiée pour tout sous-ensemble X et Y de E

f(X \cap Y) + f(X \cup Y) \le f(X) + f(Y).

(On peut définir la sous-modularité à l'aide d'autres inégalités équivalentes.)

Exemples[modifier | modifier le code]

Des exemples de fonctions sous-modulaires sont les fonctions de rang des matroïdes, ou en théorie des graphes la fonction qui associe à tout sous-ensemble de sommets d'un graphe la cardinalité de sa coupe. On trouve aussi des exemples liés à des concepts concernant l'entropie ou les probabilités.

Aspects algorithmiques[modifier | modifier le code]

Le résultat crucial des fonctions d'ensemble sous-modulaires est algorithmique:

On peut minimiser une fonction sous-modulaire en temps polynomial.

Un cas particulier est le calcul de la coupe minimum d'un graphe.

Inversement, la maximisation d'une fonction sous-modulaire définit un problème de décision NP-complet, mais sa résolution via un algorithme glouton fournit une approximation de l'optimum de qualité garantie[1].

Bibliographie[modifier | modifier le code]

Alexander Schrijver, "A combinatorial algorithm minimizing submodular functions in strongly polynomial time", Journal of Combinatorial Theory Series B, Volume 80, Issue 2 (November 2000) Pages: 346 - 355 (ISSN:0095-8956)

Notes et références[modifier | modifier le code]

  1. On pourra consulter à ce propos l'article de Nemhauser et al, "An analysis of approximations for maximizing submodular set functions", in Mathematical programming, Volume 14, Number 1, décembre 1978