liu.seSearch for publications in DiVA

References$(function(){PrimeFaces.cw("TieredMenu","widget_formSmash_upper_j_idt145",{id:"formSmash:upper:j_idt145",widgetVar:"widget_formSmash_upper_j_idt145",autoDisplay:true,overlay:true,my:"left top",at:"left bottom",trigger:"formSmash:upper:referencesLink",triggerEvent:"click"});}); $(function(){PrimeFaces.cw("OverlayPanel","widget_formSmash_upper_j_idt146_j_idt148",{id:"formSmash:upper:j_idt146:j_idt148",widgetVar:"widget_formSmash_upper_j_idt146_j_idt148",target:"formSmash:upper:j_idt146:permLink",showEffect:"blind",hideEffect:"fade",my:"right top",at:"right bottom",showCloseIcon:true});});

Tight Approximability Results for the Maximum Solution Equation Problem over Z_{p}PrimeFaces.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: Mathematical Foundations of Computer Science 2005: 30th International Symposium, MFCS 2005, Gdansk, Poland, August 29–September 2, 2005. Proceedings / [ed] Joanna Je¸drzejowicz and Andrzej Szepietowski, Springer Berlin/Heidelberg, 2005, , 628-639 p.628-639 p.Chapter in book (Refereed)
##### Abstract [en]

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

Springer Berlin/Heidelberg, 2005. , 628-639 p.628-639 p.
##### Series

Lecture Notes in Computer Science, ISSN 0302-9743 (print), 1611-3349 (online) ; 3618
##### Series

, Lecture Notes in Computer Science, ISSN 0302-9743 ; 3618
##### National Category

Computer Science
##### Identifiers

URN: urn:nbn:se:liu:diva-31026DOI: 10.1007/11549345_54Local ID: 16729ISBN: 978-3-540-28702-5ISBN: 3-540-28702-7OAI: oai:DiVA.org:liu-31026DiVA: diva2:251849
#####

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

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

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt387",{id:"formSmash:j_idt387",widgetVar:"widget_formSmash_j_idt387",multiple:true});
Available from: 2009-10-09 Created: 2009-10-09 Last updated: 2013-10-07Bibliographically approved

In the maximum solution equation problem a collection of equations are given over some algebraic structure. The objective is to find an assignment to the variables in the equations such that all equations are satisfied and the sum of the variables is maximised. We give tight approximability results for the maximum solution equation problem when the equations are given over groups of the form **Z**_{p}, where *p* is prime. We also prove that the weighted and unweighted versions of this problem have equal approximability thresholds. Furthermore, we show that the problem is equally hard to solve even if each equation is restricted to contain at most three variables and solvable in polynomial time if the equations are restricted to contain at most two variables. All of our results also hold for a generalised version of maximum solution equation where the elements of the group are mapped arbitrarily to non-negative integers in the objective function.

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