Cet article examine le problème de la gestion de multiples contraintes semi-modulaires. Étant donné un ensemble fini N, une fonction de coût c : N → ℝ+, r fonctions semi-modulaires monotones f₁, f₂, …, fᵣ sur N, et les exigences b₁, b₂, …, bᵣ, l'objectif est de trouver un sous-ensemble de coût minimal S ⊆ N tel que fᵢ(S) ≥ bᵢ (1 ≤ i ≤ r). Pour r = 1, il s'agit du problème bien connu de recouvrement d'ensembles semi-modulaires. Dans nos travaux précédents \cite{chekuri2022covering}, nous avons développé un algorithme d'approximation à double critère pour les grands r et un algorithme d'approximation pour le cas particulier important où chaque fᵢ est une fonction de recouvrement pondérée. Ces modèles sont assez généraux et incluent de nombreux cas particuliers spécifiques et intéressants. Français Le rapport d'approximation pour ces problèmes est inévitablement au moins Ω(log r) lorsque r fait partie de l'entrée. Dans cet article, inspiré par des applications récentes, nous considérons le cas où r est une constante fixe et obtenons deux résultats principaux. Lorsque nous traitons de multiples contraintes semi-modulaires, nous obtenons un algorithme d'approximation à double critère randomisé qui produit un ensemble S tel que fᵢ(S) ≥ (1-1/e^α -ε)bᵢ et E[c(S)] ≤ (1+ε)α · OPT pour chaque i ∈ [r] pour un entier donné α ≥ 1. Deuxièmement, lorsque fᵢ est une fonction de couverture pondérée d'un système d'ensembles fermés supprimé, nous obtenons un LP naturel pour l'instance de couverture de l'ensemble de base, ce qui donne une approximation de (1+ε)(e/(e-1))(1+β), où β est le rapport d'approximation. Ces résultats démontrent que pour r fixe, nous pouvons obtenir une approximation presque identique à celle réalisable lorsque r = 1. Nous notons plusieurs applications qui découlent facilement de ces résultats généraux et anticipons de nombreuses autres applications à l'avenir.
