A study of search algorithms' optimization speed

Leonardo Vanneschi, Andrea Valsecchi, Giancarlo Mauri

Research output: Contribution to journalArticle

2 Citations (Scopus)

Abstract

Search algorithms are often compared by the optimization speed achieved on some sets of cost functions. Here some properties of algorithms' optimization speed are introduced and discussed. In particular, we show that determining whether a set of cost functions F admits a search algorithm having given optimization speed is an NP-complete problem. Further, we derive an explicit formula to calculate the best achievable optimization speed when F is closed under permutation. Finally, we show that the optimization speed achieved by some well-know optimization techniques can be much worse than the best theoretical value, at least on some sets of optimization benchmarks.
Original languageEnglish
Pages (from-to)256-270
JournalJournal Of Combinatorial Optimization
Volume27
Issue number2
DOIs
Publication statusPublished - 1 Jan 2014

Fingerprint Dive into the research topics of 'A study of search algorithms' optimization speed'. Together they form a unique fingerprint.

Cite this