On the complexity of submodular function minimisation on diamonds

0.00 Avg rating—0 Votes

Article ID:	iaor20117112
Volume:	8
Issue:	3
Start Page Number:	459
End Page Number:	477
Publication Date:	Aug 2011
Journal:	Discrete Optimization
Authors:	Kuivinen Fredrik
Keywords:	complexity, discrete geometry, polyhedra

Abstract:

Let $(L; ⊓, ⊔)$ equ1 be a finite lattice and let $n$ equ2 be a positive integer. A function $f : L^{n} \to ‐ R$ equ3 is said to be submodular if $f (‐ a ⊓ ‐ b) + f (‐ a ⊔ ‐ b) = f (‐ a) + f (‐ b)$ equ4 for all $‐ a, ‐ b \in L^{n}$ equ5 . In this article we study submodular functions when $L$ equ6 is a diamond. Given oracle access to $f$ equ7 we are interested in finding $‐ x \in L^{n}$ equ8 such that $f (‐ x) = {min}_{‐ y \in L^{n}} f (‐ y)$ equ9 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 : L^{n} \to ‐ Z

and an integer

m

such that

{min}_{‐ x \in L^{n}} f (‐ x) = m

, there is a proof of this fact which can be verified in time polynomial in

n

and

{max}_{‐ t \in L^{n}} log | f (‐ t) |

; and

a pseudopolynomial‐time algorithm for the minimisation problem, i.e., given an oracle for computing a submodular

f : L^{n} \to ‐ Z

one can find

{min}_{‐ t \in L^{n}} f (‐ t)

in time bounded by a polynomial in

n

and

{max}_{‐ t \in L^{n}} | f (‐ t) |

Reviews

Required fields are marked *. Your email address will not be published.