A study of search algorithms' optimization speed

Leonardo Vanneschi, Andrea Valsecchi, Giancarlo Mauri

Research output: Contribution to journalArticlepeer-review

2 Citations (Scopus)


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
Issue number2
Publication statusPublished - 1 Jan 2014


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

Cite this