Fonction sous-modulaire

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

En optimisation combinatoire, les fonctions sous-modulaires sont des fonctions d'ensemble particulières.

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).

Les fonctions sous-modulaire peuvent être vues comme l'analogue discret des fonctions convexes.

Définition[modifier | modifier le code]

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).

Une définition équivalent est que pout tout X, Y \subseteq \Omega avec  X \subseteq Y et tout x \in \Omega \backslash Y on a : f(X\cup \{x\})-f(X)\geq f(Y\cup \{x\})-f(Y). Cette définition est parfois appelée loi des rendements décroissants, notamment dans l'application à l'économie[1].

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[2]. On trouve aussi des exemples en théorie de l'information, comme l'entropie de Shannon, ou dans la théorie des probabilités.

Les fonctions sous-modulaire peuvent être vues comme l'analogue discret des fonctions convexes[3].

Aspects algorithmiques[modifier | modifier le code]

Le résultat important en algorithmique à propos des fonctions sous-modulaires est le suivant :

On peut minimiser une fonction sous-modulaire en temps (fortement) polynomial[2].

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

A contrario, 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 un algorithme d'approximation[4].

Bibliographie[modifier | modifier le code]

  • Alexander Schrijver, « A Combinatorial Algorithm Minimizing Submodular Functions in Strongly Polynomial Time », J. Comb. Theory, Ser. B, vol. 80, no 2,‎ , p. 346-355

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

  1. Andreas Krause et Daniel Golovin, « Submodular Function Maximization », sur École polytechnique fédérale de Zurich,‎ 2012.
  2. a et b Alexander Schrijver, « A Combinatorial Algorithm Minimizing Submodular Functions in Strongly Polynomial Time », J. Comb. Theory, Ser. B, vol. 80, no 2,‎ , p. 346-355
  3. László Lovász, « Submodular functions and convexity », Mathematical Programming The State of the Art,‎ , p. 235-257 (lire en ligne)
  4. George L Nemhauser, Laurence A Wolsey et Marshall L Fisher, « An analysis of approximations for maximizing submodular set functions—I », Mathematical Programming, vol. 14, no 1,‎ , p. 265-294.