On the Complexity of Submodular Function Minimisation on Diamonds

Fredrik Kuivinen

Let $(L;\sqcap ,\bigsqcup )$ be a finite lattice and let $n$ be a positive integer. A function $f:L^n\to \mathbb{R}$ is said to be submodular if $f(\tup{a} \sqcap \tup{b}) + f(\tup…