wiki_research

personal research wiki
git clone https://a3nm.net/git/wiki_research/
Log | Files | Refs

submodular_set_function (491B)

      1 # Submodular set function
      2 
      3 https://en.wikipedia.org/wiki/Submodular_set_function
      4 
      5 function f on sets such that f(X cup {z}) - f(X) >= f(Y cup {z}) - f(Y)
      6 whenever X \subseteq Y
      7 
      8 Implies being [subadditive], converse is not true in general
      9 
     10 Special case discussed in [zivny2009expressive]: [submodular_set_function_bounded_arity], a sum of [submodular_set_functions] defined on a bounded subset of variables
     11 
     12 See also: [submodular_optimization], [concave_function]
     13 
     14 Up: [submodular_function]