Polynomial Algorithms to Minimize 2/3-Submodular Functions

It is a fundamental result in combinatorial optimization that submodular functions can be minimized in polynomial-time. This paper considers the minimization problem for a more general class of set functions that contains all submodular functions. A set function is called 2/3-submodular if the submodular inequality holds for at least two pairs formed from every distinct three subsets. This paper provides two weakly polynomial-time algorithms to minimize 2/3-submodular functions, which yield an efficient algorithm to obtain color assignments of a variant of the supermodular coloring theorem.