  This paper considers the minimization problem of relaxed submodular
functions. For a positive integer $k$, a set function is called $k$-distant
submodular if the submodular inequality holds for every pair whose symmetric
difference is at least $k$. This paper provides a polynomial time algorithm to
minimize $k$-distant submodular functions for a fixed positive integer $k$.
This result generalizes the tractable result of minimizing 2/3-submodular
functions, which satisfy the submodular inequality for at least two pairs
formed from every distinct three sets.
