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]