<p>A fundamental result in combinatorial optimization is that submodular functions can be minimized in polynomial-time. In this paper, we consider 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. In this paper, we provide two weakly polynomial-time algorithms to minimize 2/3-submodular functions. We also present a min-max theorem for 2/3-submodular functions, which extends the celebrated min-max theorem for submodular functions.</p>