liu.seSearch for publications in DiVA

CiteExport$(function(){PrimeFaces.cw("TieredMenu","widget_formSmash_upper_j_idt144",{id:"formSmash:upper:j_idt144",widgetVar:"widget_formSmash_upper_j_idt144",autoDisplay:true,overlay:true,my:"left top",at:"left bottom",trigger:"formSmash:upper:exportLink",triggerEvent:"click"});}); $(function(){PrimeFaces.cw("OverlayPanel","widget_formSmash_upper_j_idt145_j_idt147",{id:"formSmash:upper:j_idt145:j_idt147",widgetVar:"widget_formSmash_upper_j_idt145_j_idt147",target:"formSmash:upper:j_idt145:permLink",showEffect:"blind",hideEffect:"fade",my:"right top",at:"right bottom",showCloseIcon:true});});

Aspects of a Constraint Optimisation ProblemPrimeFaces.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();
}
}
2010 (English)Doctoral thesis, monograph (Other academic)
##### Abstract [en]

##### Place, publisher, year, edition, pages

Linköping: Linköping University Electronic Press , 2010. , p. 218
##### Series

Linköping Studies in Science and Technology. Dissertations, ISSN 0345-7524 ; 1294
##### National Category

Engineering and Technology
##### Identifiers

URN: urn:nbn:se:liu:diva-52103ISBN: 978-91-7393-464-0 (print)OAI: oai:DiVA.org:liu-52103DiVA, id: diva2:281774
##### Public defence

2010-02-05, Visionen, hus B, Campus Valla, Linköpings universitet, Linköping, 13:15 (English)
##### Opponent

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt434",{id:"formSmash:j_idt434",widgetVar:"widget_formSmash_j_idt434",multiple:true});
##### Supervisors

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

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt446",{id:"formSmash:j_idt446",widgetVar:"widget_formSmash_j_idt446",multiple:true}); Available from: 2009-12-21 Created: 2009-12-04 Last updated: 2009-12-21Bibliographically approved

In this thesis we study a constraint optimisation problem called the maximum solution problem, henceforth referred to as Max Sol. It is defined as the problem of optimising a linear objective function over a constraint satisfaction problem (Csp) instance on a finite domain. Each variable in the instance is given a non-negative rational weight, and each domain element is also assigned a numerical value, for example taken from the natural numbers. From this point of view, the problem is seen to be a natural extension of integer linear programming over a bounded domain. We study both the time complexity of approximating Max Sol, and the time complexity of obtaining an optimal solution. In the latter case, we also construct some exponential-time algorithms.

The algebraic method is a powerful tool for studying Csp-related problems. It was introduced for the decision version of Csp, and has been extended to a number of other problems, including Max Sol. With this technique we establish approximability classifications for certain families of constraint languages, based on algebraic characterisations. We also show how the concept of a core for relational structures can be extended in order to determine when constant unary relations can be added to a constraint language, without changing the computational complexity of finding an optimal solution to Max Sol. Using this result we show that, in a specific sense, when studying the computational complexity of Max Sol, we only need to consider constraint languages with all constant unary relations included.

Some optimisation problems are known to be approximable within some constant ratio, but are not believed to be approximable within an arbitrarily small constant ratio. For such problems, it is of interest to find the best ratio within which the problem can be approximated, or at least give some bounds on this constant. We study this aspect of the (weighted) Max Csp problem for graphs. In this optimisation problem the number of satisfied constraints is supposed to be maximised. We introduce a method for studying approximation ratios which is based on a new parameter on the space of all graphs. Informally, we think of this parameter as an approximation distance; knowing the distance between two graphs, we can bound the approximation ratio of one of them, given a bound for the other. We further show how the basic idea can be implemented also for the Max Sol problem.

isbn
urn-nbn$(function(){PrimeFaces.cw("Tooltip","widget_formSmash_j_idt1156",{id:"formSmash:j_idt1156",widgetVar:"widget_formSmash_j_idt1156",showEffect:"fade",hideEffect:"fade",showDelay:500,hideDelay:300,target:"formSmash:altmetricDiv"});});

CiteExport$(function(){PrimeFaces.cw("TieredMenu","widget_formSmash_lower_j_idt1209",{id:"formSmash:lower:j_idt1209",widgetVar:"widget_formSmash_lower_j_idt1209",autoDisplay:true,overlay:true,my:"left top",at:"left bottom",trigger:"formSmash:lower:exportLink",triggerEvent:"click"});}); $(function(){PrimeFaces.cw("OverlayPanel","widget_formSmash_lower_j_idt1210_j_idt1212",{id:"formSmash:lower:j_idt1210:j_idt1212",widgetVar:"widget_formSmash_lower_j_idt1210_j_idt1212",target:"formSmash:lower:j_idt1210:permLink",showEffect:"blind",hideEffect:"fade",my:"right top",at:"right bottom",showCloseIcon:true});});