Minimisation des fonctions submodulaires

Cette séance de cours couvre le concept de fonctions sous-modulaires et leur minimisation, définissant la sous-modularité comme f(A) + f(B) > f(AUB) + f(AMB) pour tous les sous-ensembles A, B de l'ensemble de base N. Elle explique également l'intuition derrière la sous-modularité, en se concentrant sur les rendements décroissants. Des exemples de fonctions sous-modulaires, telles que les fonctions de coupe de graphique, sont fournis pour illustrer le concept. L'instructeur discute de l'extension Lovsz et de son rôle dans la minimisation des fonctions sous-modulaires, en soulignant l'uniformité de l'extension. La séance de cours se termine par l'application de fonctions sous-modulaires dans la maximisation de l'influence, où l'objectif est de sélectionner un ensemble d'individus pour maximiser la propagation de l'influence dans un réseau.