On the complexity of submodular function minimisation on diamonds

Let (L;⊓,⊔)(L;⊓,⊔) be a finite lattice and let nn be a positive integer. A function f:Ln→Rf:Ln→R is said to be submodular   if f(a⊓b)+f(a⊔b)≤f(a)+f(b) for all a,b∈Ln. In this article we study submodular functions when LL is a diamond  . Given oracle access to ff we are interested in finding x∈Ln such that f(x)=miny∈Lnf(y) as efficiently as possible. We establish
• a min–max theorem, which states that the minimum of the submodular function is equal to the maximum of a certain function defined over a certain polyhedron; and
• a good characterisation of the minimisation problem, i.e., we show that given an oracle for computing a submodular f:Ln→Zf:Ln→Z and an integer mm such that minx∈Lnf(x)=m, there is a proof of this fact which can be verified in time polynomial in nn and maxt∈Lnlog|f(t)|; and
• a pseudopolynomial-time algorithm for the minimisation problem, i.e., given an oracle for computing a submodular f:Ln→Zf:Ln→Z one can find mint∈Lnf(t) in time bounded by a polynomial in nn and maxt∈Ln|f(t)|.