Fonction sous-modulaire

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

${\displaystyle f(X\cap Y)+f(X\cup Y)\leq f(X)+f(Y).}$

Une définition équivalente est que pour tout ${\displaystyle X,Y\subseteq \Omega }$ avec ${\displaystyle X\subseteq Y}$ et tout ${\displaystyle x\in \Omega \backslash Y}$ on a : ${\displaystyle 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[2].

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

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[3].

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]. Le problème de couverture maximale est un exemple de telle maximisation.

Ce type de fonction apparait en apprentissage automatique. Par exemple, en sélection de caractéristique, étant donné des données de grande dimension, on cherche à trouver un petit ensemble de variables qui soit les plus pertinentes, et cette pertinence peut parfois être représentée par une fonction sous-modulaire.

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