liu.seSearch for publications in DiVA

References$(function(){PrimeFaces.cw("TieredMenu","widget_formSmash_upper_j_idt152",{id:"formSmash:upper:j_idt152",widgetVar:"widget_formSmash_upper_j_idt152",autoDisplay:true,overlay:true,my:"left top",at:"left bottom",trigger:"formSmash:upper:referencesLink",triggerEvent:"click"});}); $(function(){PrimeFaces.cw("OverlayPanel","widget_formSmash_upper_j_idt153_j_idt155",{id:"formSmash:upper:j_idt153:j_idt155",widgetVar:"widget_formSmash_upper_j_idt153_j_idt155",target:"formSmash:upper:j_idt153:permLink",showEffect:"blind",hideEffect:"fade",my:"right top",at:"right bottom",showCloseIcon:true});});

On the complexity of submodular function minimisation on diamondsPrimeFaces.cw("AccordionPanel","widget_formSmash_some",{id:"formSmash:some",widgetVar:"widget_formSmash_some",multiple:true}); PrimeFaces.cw("AccordionPanel","widget_formSmash_all",{id:"formSmash:all",widgetVar:"widget_formSmash_all",multiple:true});
function selectAll()
{
var panelSome = $(PrimeFaces.escapeClientId("formSmash:some"));
var panelAll = $(PrimeFaces.escapeClientId("formSmash:all"));
panelAll.toggle();
toggleList(panelSome.get(0).childNodes, panelAll);
toggleList(panelAll.get(0).childNodes, panelAll);
}
/*Toggling the list of authorPanel nodes according to the toggling of the closeable second panel */
function toggleList(childList, panel)
{
var panelWasOpen = (panel.get(0).style.display == 'none');
// console.log('panel was open ' + panelWasOpen);
for (var c = 0; c < childList.length; c++) {
if (childList[c].classList.contains('authorPanel')) {
clickNode(panelWasOpen, childList[c]);
}
}
}
/*nodes have styleClass ui-corner-top if they are expanded and ui-corner-all if they are collapsed */
function clickNode(collapse, child)
{
if (collapse && child.classList.contains('ui-corner-top')) {
// console.log('collapse');
child.click();
}
if (!collapse && child.classList.contains('ui-corner-all')) {
// console.log('expand');
child.click();
}
}
PrimeFaces.cw("AccordionPanel","widget_formSmash_responsibleOrgs",{id:"formSmash:responsibleOrgs",widgetVar:"widget_formSmash_responsibleOrgs",multiple:true}); 2011 (English)In: Discrete Optimization, ISSN 1572-5286, Vol. 8, no 3, 459-477 p.Article in journal (Refereed) Published
##### Abstract [en]

##### 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
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt400",{id:"formSmash:j_idt400",widgetVar:"widget_formSmash_j_idt400",multiple:true});
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt406",{id:"formSmash:j_idt406",widgetVar:"widget_formSmash_j_idt406",multiple:true});
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt413",{id:"formSmash:j_idt413",widgetVar:"widget_formSmash_j_idt413",multiple:true});
##### Note

Funding Agencies|National Graduate School in Computer Science (CUGS), Sweden||Available from: 2011-09-02 Created: 2011-09-02 Last updated: 2011-09-02

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.

References$(function(){PrimeFaces.cw("TieredMenu","widget_formSmash_lower_j_idt1144",{id:"formSmash:lower:j_idt1144",widgetVar:"widget_formSmash_lower_j_idt1144",autoDisplay:true,overlay:true,my:"left top",at:"left bottom",trigger:"formSmash:lower:referencesLink",triggerEvent:"click"});}); $(function(){PrimeFaces.cw("OverlayPanel","widget_formSmash_lower_j_idt1145_j_idt1147",{id:"formSmash:lower:j_idt1145:j_idt1147",widgetVar:"widget_formSmash_lower_j_idt1145_j_idt1147",target:"formSmash:lower:j_idt1145:permLink",showEffect:"blind",hideEffect:"fade",my:"right top",at:"right bottom",showCloseIcon:true});});