liu.seSearch for publications in DiVA
Change search

Cite
Citation style
• apa
• harvard1
• ieee
• modern-language-association-8th-edition
• vancouver
• oxford
• Other style
More styles
Language
• de-DE
• en-GB
• en-US
• fi-FI
• nn-NO
• nn-NB
• sv-SE
• Other locale
More languages
Output format
• html
• text
• asciidoc
• rtf
On the complexity of submodular function minimisation on diamonds
Linköping University, Department of Computer and Information Science, TCSLAB - Theoretical Computer Science Laboratory. Linköping University, The Institute of Technology.
2011 (English)In: Discrete Optimization, ISSN 1572-5286, E-ISSN 1873-636X, Vol. 8, no 3, 459-477 p.Article in journal (Refereed) Published
##### Abstract [en]

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.
##### Keyword [en]
Combinatorial optimization, Submodular function minimization, Lattices, Diamonds
##### National Category
Medical and Health Sciences
##### Identifiers
ISI: 000293931900007OAI: oai:DiVA.org:liu-70339DiVA: diva2:438335
##### Note
Funding Agencies|National Graduate School in Computer Science (CUGS), Sweden||Available from: 2011-09-02 Created: 2011-09-02 Last updated: 2017-12-08

#### Open Access in DiVA

No full text

Publisher's full text

#### Authority records BETA

Kuivinen, Fredrik

#### Search in DiVA

##### By author/editor
Kuivinen, Fredrik
##### By organisation
TCSLAB - Theoretical Computer Science LaboratoryThe Institute of Technology
##### In the same journal
Discrete Optimization
##### On the subject
Medical and Health Sciences

doi
urn-nbn

#### Altmetric score

doi
urn-nbn
Total: 18 hits

Cite
Citation style
• apa
• harvard1
• ieee
• modern-language-association-8th-edition
• vancouver
• oxford
• Other style
More styles
Language
• de-DE
• en-GB
• en-US
• fi-FI
• nn-NO
• nn-NB
• sv-SE
• Other locale
More languages
Output format
• html
• text
• asciidoc
• rtf