A study of search algorithms’ optimization speed

Andrea Valsecchi (), Leonardo Vanneschi () and Giancarlo Mauri ()
Additional contact information
Andrea Valsecchi: European Centre for Soft Computing
Leonardo Vanneschi: Università di Milano-Bicocca
Giancarlo Mauri: Università di Milano-Bicocca

Journal of Combinatorial Optimization, 2014, vol. 27, issue 2, No 4, 256-270

Abstract: 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.

Keywords: Optimization problems; Search algorithms; Optimization speed (search for similar items in EconPapers)
Date: 2014
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-012-9514-7 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:27:y:2014:i:2:d:10.1007_s10878-012-9514-7

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-012-9514-7

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().