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

On Some Combinatorial Optimization Problems: Algorithms and ComplexityPrimeFaces.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();
}
}
2015 (English)Doctoral thesis, comprehensive summary (Other academic)
##### Abstract [en]

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

Linköping: Linköping University Electronic Press, 2015. , p. 32
##### Series

Linköping Studies in Science and Technology. Dissertations, ISSN 0345-7524 ; 1663
##### Keywords [en]

Computational complexity, optimization, constraint satisfaction problem
##### National Category

Computer Sciences
##### Identifiers

URN: urn:nbn:se:liu:diva-116859DOI: 10.3384/diss.diva-116859ISBN: 978-91-7519-072-3 (print)OAI: oai:DiVA.org:liu-116859DiVA, id: diva2:806491
##### Public defence

2015-05-21, Alan Turing, E-huset, Campus Valla, Linköping, 13:15 (English)
##### Opponent

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

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

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt476",{id:"formSmash:j_idt476",widgetVar:"widget_formSmash_j_idt476",multiple:true});
##### Funder

CUGS (National Graduate School in Computer Science), 09.01Available from: 2015-04-23 Created: 2015-04-07 Last updated: 2018-01-11Bibliographically approved
##### List of papers

This thesis is about the computational complexity of several classes of combinatorial optimization problems, all related to the constraint satisfaction problems.

A constraint language consists of a domain and a set of relations on the domain. For each such language there is a constraint satisfaction problem (CSP). In this problem we are given a set of variables and a collection of constraints, each of which is constraining some variables with a relation in the language. The goal is to determine if domain values can be assigned to the variables in a way that satisfies all constraints. An important question is for which constraint languages the corresponding CSP can be solved in polynomial time. We study this kind of question for optimization problems related to the CSPs.

The main focus is on extended minimum cost homomorphism problems. These are optimization versions of CSPs where instances come with an objective function given by a weighted sum of unary cost functions, and where the goal is not only to determine if a solution exists, but to find one of minimum cost. We prove a complete classification of the complexity for these problems on three-element domains. We also obtain a classification for the so-called conservative case.

Another class of combinatorial optimization problems are the surjective maximum CSPs. These problems are variants of CSPs where a non-negative weight is attached to each constraint, and the objective is to find a surjective mapping of the variables to values that maximizes the weighted sum of satisfied constraints. The surjectivity requirement causes these problems to behave quite different from for example the minimum cost homomorphism problems, and many powerful techniques are not applicable. We prove a dichotomy for the complexity of the problems in this class on two-element domains. An essential ingredient in the proof is an algorithm that solves a generalized version of the minimum cut problem. This algorithm might be of independent interest.

In a final part we study properties of NP-hard optimization problems. This is done with the aid of restricted forms of polynomial-time reductions that for example preserves solvability in sub-exponential time. Two classes of optimization problems similar to those discussed above are considered, and for both we obtain what may be called an easiest NP-hard problem. We also establish some connections to the exponential time hypothesis.

1. Max-Sur-CSP on Two Elements$(function(){PrimeFaces.cw("OverlayPanel","overlay543175",{id:"formSmash:j_idt538:0:j_idt542",widgetVar:"overlay543175",target:"formSmash:j_idt538:0:partsLink",showEvent:"mousedown",hideEvent:"mousedown",showEffect:"blind",hideEffect:"fade",appendToBody:true});});

2. The Complexity of Three-Element Min-Sol and Conservative Min-Cost-Hom$(function(){PrimeFaces.cw("OverlayPanel","overlay680731",{id:"formSmash:j_idt538:1:j_idt542",widgetVar:"overlay680731",target:"formSmash:j_idt538:1:partsLink",showEvent:"mousedown",hideEvent:"mousedown",showEffect:"blind",hideEffect:"fade",appendToBody:true});});

3. Computational Complexity of the Minimum Cost Homomorphism Problem on Three-element Domains$(function(){PrimeFaces.cw("OverlayPanel","overlay773698",{id:"formSmash:j_idt538:2:j_idt542",widgetVar:"overlay773698",target:"formSmash:j_idt538:2:partsLink",showEvent:"mousedown",hideEvent:"mousedown",showEffect:"blind",hideEffect:"fade",appendToBody:true});});

4. Relating the Time Complexity of Optimization Problems in Light of the Exponential-Time Hypothesis$(function(){PrimeFaces.cw("OverlayPanel","overlay773656",{id:"formSmash:j_idt538:3:j_idt542",widgetVar:"overlay773656",target:"formSmash:j_idt538:3:partsLink",showEvent:"mousedown",hideEvent:"mousedown",showEffect:"blind",hideEffect:"fade",appendToBody:true});});

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

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