On the complexity of submodular function minimisation on diamonds
2011 (English)In: Discrete Optimization, ISSN 1572-5286, Vol. 8, no 3, 459-477 p.Article in journal (Refereed) Published
Let (L: boolean AND, boolean OR) be a finite lattice and let n be a positive integer. A function f : L(n) -andgt; R is said to be submodular if f(a boolean AND b) + f(a boolean OR b) andlt;= f(a) + f(b) for all a, b is an element of L(n). In this article we study submodular functions when L is a diamond. Given oracle access to f we are interested in finding x is an element of L(n) such that f(x) = min(y is an element of Ln) f(y) as efficiently as possible. We establish less thanbrgreater than less thanbrgreater thana 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 less thanbrgreater than less thanbrgreater thana good characterisation of the minimisation problem, i.e., we show that given an oracle for computing a submodular f : L(n) -andgt; Z and an integer m such that min(x is an element of Ln) f(x) = there is a proof of this fact which can be verified in time polynomial in n and max(t is an element of Ln) log vertical bar f(t)vertical bar; and less thanbrgreater than less thanbrgreater thana pseudopolynomial-time algorithm for the minimisation problem, i.e., given an oracle for computing a submodular f : L(n) -andgt; Z one can find min(t is an element of Ln) f(t) in time bounded by a polynomial in n and max(t is an element of Ln) vertical bar f(t)vertical bar.
Place, publisher, year, edition, pages
Elsevier , 2011. Vol. 8, no 3, 459-477 p.
Combinatorial optimization, Submodular function minimization, Lattices, Diamonds
Medical and Health Sciences
IdentifiersURN: urn:nbn:se:liu:diva-70339DOI: 10.1016/j.disopt.2011.04.001ISI: 000293931900007OAI: oai:DiVA.org:liu-70339DiVA: diva2:438335
Funding Agencies|National Graduate School in Computer Science (CUGS), Sweden||2011-09-022011-09-022011-09-02