wiki_research

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

zivny2009expressive (586B)


      1 # zivny2009expressive
      2 
      3 [submodular_set_function_bounded_arity], a sum of [submodular_set_functions] defined on a bounded subset of [variables]
      4 
      5 talks about [submodular_polynomial], and quadratic submodular polynomials, which admit a more efficient optimization algorithm by reduction to [min_cut]
      6 
      7 all cubic submodular polynomials can be expressed as quadratic submodular polynomials, but for degree-4 this is no longer true and they characterize which ones are expressible
      8 - the [computational_complexity] of recognizing them is open
      9 
     10 Up: [academic_paper] on [submodular_set_function]