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_idt156",{id:"formSmash:upper:j_idt153:j_idt156",widgetVar:"widget_formSmash_upper_j_idt153_j_idt156",target:"formSmash:upper:j_idt153:permLink",showEffect:"blind",hideEffect:"fade",my:"right top",at:"right bottom",showCloseIcon:true});});

Beating a Random Assignment: Approximating Constraint Satisfaction ProblemsPrimeFaces.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}); 2005 (English)Doctoral thesis, monograph (Other scientific)
##### Abstract [en]

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

Stockholm: KTH , 2005. , x, 102 p.
##### Series

Trita-NA, ISSN 0348-2952 ; 0513
##### Keyword [sv]

Datalogi
##### National Category

Computer Science
##### Identifiers

URN: urn:nbn:se:kth:diva-215ISBN: 91-7178-051-3OAI: oai:DiVA.org:kth-215DiVA: diva2:7927
##### Public defence

2005-06-14, E3, Osquars backe 14, Stockholm, 14:15
##### Opponent

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

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

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

QC 20101020Available from: 2005-05-24 Created: 2005-05-24 Last updated: 2010-10-20Bibliographically approved

An instance of a Boolean constraint satisfaction problem, CSP, consists of a set of constraints acting over a set of Boolean variables. The objective is to find an assignment to the variables that satisfies all the constraints. In the maximization version, Max CSP, each constraint has a weight and the objective is to find an assignment such that the weight of satisfied constraints is maximized. By specifying which types of constraints that are allowed we create subproblems to Max CSP. For example, an instance of Max kCSP only contains constraints that act over at most k different variables. Another problem is Max CSP(P), where P is a predicate, i.e., a Boolean function. In such an instance P is used to determine if a constraint is satisfied or not.

Both Max kCSP and Max CSP(P) are NP-hard to solve optimally for k ≥ 2 and predicates P that depend on at least two input values. Therefore, we consider efficient approximation algorithms for these two problems. A trivial algorithm is to assign all variables a random value. Somewhat surprisingly, Håstad showed that using this random assignment approach is essentially optimal for approximating Max CSP(P), for some predicates P. We call such predicates approximation resistant. Goemans and Williamson introduced an approximation method that relaxes problems into semidefinite programs. Using this method they show that for predicates P of arity two, it is possible to outperform a random assignment in approximating Max CSP(P). By extending this technique Zwick characterized all predicates of arity three as either approximation resistant or not.

In this thesis we consider predicates of arity larger than three. We extend the work of Håstad and the work of Samorodnitsky and Trevisan in order to show predicates to be approximation resistant. We also use semidefinite relaxation algorithms in order to show that predicates are not approximation resistant. In particular we show that predicates with few non-accepting inputs are approximation resistant and that predicates with few accepting inputs are not approximation resistant. We study predicates of arity four more closely and characterize 354 out of 400 predicate types.

Max kCSP is 2^{-k}-approximated by a random assignment and previously no algorithms were known to outperform such an algorithm with more than a small constant factor. In this thesis a probabilistic

Ω (2^{k+log k-log log k})-approximation for Max kCSP is presented.

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