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 assignmentPrimeFaces.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)In: APPROXIMATION, RANDOMIZATION AND COMBINATORIAL OPTIMIZATION: ALGORITHMS AND TECHNIQUES / [ed] Chekuri, C; Jansen, K; Rolim, JDP; Trevisan, L, 2005, Vol. 3624, 134-145 p.Conference paper (Refereed)
##### Abstract [en]

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

2005. Vol. 3624, 134-145 p.
##### Series

, LECTURE NOTES IN COMPUTER SCIENCE, ISSN 0302-9743 ; 3624
##### National Category

Computer and Information Science
##### Identifiers

URN: urn:nbn:se:kth:diva-42724ISI: 000232240900012ScopusID: 2-s2.0-26944440861ISBN: 3-540-28239-4OAI: oai:DiVA.org:kth-42724DiVA: diva2:448083
##### Conference

8th International Workshop on Approxination Algorithms for Combinatorial Optimization Problems/9th International Workshop on Randomization and Computation Location: Berkeley, CA Date: AUG 22-24, 2005
#####

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

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 20111014Available from: 2011-10-14 Created: 2011-10-12 Last updated: 2011-10-14Bibliographically approved

MAX CSP(P) is the problem of maximizing the weight of satisfied constraints, where each constraint acts over a k-tuple of literals and is evaluated using the predicate P. The approximation ratio of a random assignment is equal to the fraction of satisfying inputs to P. If it is NP-hard to achieve a better approximation ratio for MAX CSP(P), then we say that P is approximation resistant. Our goal is to characterize which predicates that have this property. A general approximation algorithm for MAX CSP(P) is introduced. For a multitude of different P, it is shown that the algorithm beats the random assignment algorithm, thus implying that P is not approximation resistant. In particular, over 2/3 of the predicates on four binary inputs are proved not to be approximation resistant, as well as all predicates on 2s binary inputs, that have at most 2s + I accepting inputs. We also prove a large number of predicates to be approximation resistant. In particular, all predicates of arity 2s + s(2) with less than 2(s2) nonaccepting inputs axe proved to be approximation resistant, as well as almost 1/5 of the predicates on four binary inputs.

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});});