submodularitet

Submodularitet er en egenskab ved visse funktioner defineret på delmængder af en given mængde N. En funktion f: 2^N → R er submodulær hvis for alle A ⊆ B ⊆ N og alle x ∉ B gælder f(A) + f(B ∪ {x}) ≤ f(A ∪ {x}) + f(B). Dette kan også udtrykkes som at marginalgevinsten ved at tilføje et element x til en mindre mængde er større eller lig den marginale gevinst ved at tilføje x til en større mængde: f(A ∪ {x}) − f(A) ≥ f(B ∪ {x}) − f(B). Submodularitet beskriver dermed udbytte-dæmpning (diminishing returns).

Funktioner kan være normaliserede (f(∅) = 0) og/eller monotone (A ⊆ B ⇒ f(A) ≤ f(B)). Mange praktiske funktioner er både submodulære og monotone, hvilket gør dem særligt velegnede til optimering.

Eksempler: grafens cut-funktion er submodular; entropi er submodular; dækningsfunktion f(S) = |⋃_{i∈S} U_i| er submodular og ofte monotone.

Anvendelser: submodularitet optræder i opgaver som udvælgelse af undergrupper i dataudtræk, placering af sensorer, feature selection og influenzemaximering i sociale netværk. Underliggende mål er ofte at maksimere en submodulær funktion under tællebegrænsninger eller budgetter.

Algoritmisk konsekvens: for monotone submodulære funktioner under en kardinalitetsbegrænsning k giver den greedy-tilgang en garanti på mindst (1 − 1/e) ≈ 0,632 af optimum. Submodularitet tillader dermed effektive approksimationsalgoritmer og teoretiske garantier, der ikke kræver fuld optimal løsning.