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 tous sous-ensembles 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 E}$ avec ${\displaystyle X\subseteq Y}$ et tout ${\displaystyle x\in E\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.