liu.seSearch for publications in DiVA
Change search
CiteExportLink to record
Permanent link

Direct link
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
URN: urn:nbn:se:liu:diva-70339DOI: 10.1016/j.disopt.2011.04.001ISI: 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

Other links

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
Medical and Health Sciences

Search outside of DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetric score

doi
urn-nbn
Total: 18 hits
CiteExportLink to record
Permanent link

Direct link
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