Heuristics for NP-hard optimization problems

Abstract

    <jats:p> We provide several examples showing that local search, the most basic metaheuristics, may be a very competitive choice for solving computationally hard optimization problems. In addition, generation of starting solutions by greedy heuristics should be at least considered as one of very natural possibilities. In this critical survey, selected examples discussed include the traveling salesman, the resource-constrained project scheduling, the channel assignment, and computation of bounds for the Shannon capacity.

Document type: Article

Full document

Original document

The different versions of the original document can be found in:

• https://content.sciendo.com/downloadpdf/journals/jlst/6/1/article-p1.pdf under the license https://creativecommons.org/licenses/by-nc-nd

• http://content.sciendo.com/view/journals/jlst/6/1/article-p1.xml,

https://www.degruyter.com/view/j/jlst.2015.6.issue-1/jlst-2015-0006/jlst-2015-0006.pdf,

http://dx.doi.org/10.1515/jlst-2015-0006 under the license cc-by-nc-nd

• http://www.degruyter.com/view/j/jlst.2015.6.issue-1/jlst-2015-0006/jlst-2015-0006.xml?format=INT,

https://doaj.org/toc/2232-4968 under the license http://creativecommons.org/licenses/by-nc-nd/4.0

• https://content.sciendo.com/view/journals/jlst/6/1/article-p1.xml?language=en,

https://www.degruyter.com/downloadpdf/j/jlst.2015.6.issue-1/jlst-2015-0006/jlst-2015-0006.xml,

https://dk.um.si/IzpisGradiva.php?id=69004,

http://iclst.fl.uni-mb.si/pdf/2014/Zerovnik_Heuristics%20for%20NP-hard%20optimization%20problems%20.pdf,

https://ideas.repec.org/a/vrs/losutr/v6y2015i1p1-10n1.html,

https://trid.trb.org/view/1396153,

https://www.growkudos.com/publications/10.1515%252Fjlst-2015-0006,

https://econpapers.repec.org/article/vrslosutr/v_3a6_3ay_3a2015_3ai_3a1_3ap_3a1-10_3an_3a1.htm,

https://socionet.ru/publication.xml?h=repec:vrs:losutr:v:6:y:2015:i:1:p:1-10:n:1,

https://core.ac.uk/display/88594658,

https://academic.microsoft.com/#/detail/2282282339

• https://dk.um.si/IzpisGradiva.php?id=69004,

https://dk.um.si/Dokument.php?id=120357&dn=,

https://dk.um.si/Dokument.php?id=120356&dn=,

https://plus.si.cobiss.net/opac7/bib/14386203?lang=sl

under the license http://creativecommons.org/licenses/by-nc-nd/4.0/