On k-Submodular Relaxation

Hiroshi Hirai, Yuni Iwamasa

$k$-submodular functions, introduced by Huber and Kolmogorov, are functions defined on $\{0,1,2,\dots ,k{\}}^n$ satisfying certain submodular-type inequalities. $k$-submodular fun…