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

Using easy optimization problems to solve hard onesPrimeFaces.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}); 2004 (English)In: Classical and New Paradigms of Computation and Their Complexity Hierarchies / [ed] Lowe, B; Piwinger, B; Rasch, T, DORDRECHT: SPRINGER , 2004, Vol. 23, p. 77-93Conference paper, Published paper (Refereed)
##### Abstract [en]

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

DORDRECHT: SPRINGER , 2004. Vol. 23, p. 77-93
##### Series

Trends In Logic - Studia Logica Library, ISSN 1572-6126 ; 23
##### National Category

Computer and Information Sciences
##### Identifiers

URN: urn:nbn:se:kth:diva-44675ISI: 000229305100007ISBN: 1-4020-2775-3 (print)OAI: oai:DiVA.org:kth-44675DiVA, id: diva2:452110
##### Conference

Conference on Foundations of the Formal Sciences III Location: Vienna, AUSTRIA Date: SEP 21-24, 2001
#####

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

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

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

QC 20111028Available from: 2011-10-28 Created: 2011-10-25 Last updated: 2018-01-12Bibliographically approved

In combinatorial optimization one typically wants to minimize some cost function given a set of constraints that must be satisfied. A classical example is the so called Traveling Salesman Problem (TSP), in which we are given a set of cities with certain distances between them and we are asked to find the shortest possible tour that visits every city exactly once and then returns to the starting point. This problem is believed to be hard to solve exactly-it has been shown to belong to a certain class of notoriously hard problems, the so called NP-hard problems. Despite huge efforts, there is no currently known efficient algorithm that solves any of the NP-hard problems and it is widely believed that no such algorithm exists. However, it is always possible to find an approximation to the optimum tour by solving a much easier problem, the so called Minimum Spanning Tree problem. This is an example of a general paradigm in the field of approximation algorithms for optimization problems: Instead of solving a very hard problem we solve an easy one and then convert the optimal solution to the easy problem into an approximately optimal solution to the hard one. Obviously, it is important to be careful when converting the optimal solution to the easy problem into an approximately optimal solution to the hard one. In many applications, the analysis of the algorithm is greatly simplified by the use of random selections. Typically, we then use information obtained from the solution to the easy problem to bias our selection of a solution to the hard one.

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

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