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

On the Usefulness of PredicatesPrimeFaces.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();
}
}
2012 (English)In: Computing Research Repository, Vol. abs/1204.5662Article in journal (Refereed) Published
##### Abstract [en]

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

2012. Vol. abs/1204.5662
##### National Category

Computer Sciences
##### Identifiers

URN: urn:nbn:se:kth:diva-113297OAI: oai:DiVA.org:kth-113297DiVA, id: diva2:587588
##### Conference

CoRR
#####

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

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

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

Motivated by the pervasiveness of strong inapproximability results forMax-CSPs, we introduce a relaxed notion of an approximate solution of aMax-CSP. In this relaxed version, loosely speaking, the algorithm is allowed toreplace the constraints of an instance by some other (possibly real-valued)constraints, and then only needs to satisfy as many of the new constraints aspossible.To be more precise, we introduce the following notion of a predicate $P$being \emph{useful} for a (real-valued) objective $Q$: given an almostsatisfiable Max-$P$ instance, there is an algorithm that beats a randomassignment on the corresponding Max-$Q$ instance applied to the same sets ofliterals. The standard notion of a nontrivial approximation algorithm for aMax-CSP with predicate $P$ is exactly the same as saying that $P$ is useful for$P$ itself.We say that $P$ is useless if it is not useful for any $Q$. This turns out tobe equivalent to the following pseudo-randomness property: given an almostsatisfiable instance of Max-$P$ it is hard to find an assignment such that theinduced distribution on $k$-bit strings defined by the instance is notessentially uniform.Under the Unique Games Conjecture, we give a complete and simplecharacterization of useful Max-CSPs defined by a predicate: such a Max-CSP isuseless if and only if there is a pairwise independent distribution supportedon the satisfying assignments of the predicate. It is natural to also considerthe case when no negations are allowed in the CSP instance, and we derive asimilar complete characterization (under the UGC) there as well.Finally, we also include some results and examples shedding additional lighton the approximability of certain Max-CSPs.

QC 20130506

Available from: 2013-01-14 Created: 2013-01-14 Last updated: 2018-01-11Bibliographically approved
urn-nbn$(function(){PrimeFaces.cw("Tooltip","widget_formSmash_j_idt1844",{id:"formSmash:j_idt1844",widgetVar:"widget_formSmash_j_idt1844",showEffect:"fade",hideEffect:"fade",showDelay:500,hideDelay:300,target:"formSmash:altmetricDiv"});});

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