Int. J. of Metaheuristics   »   2011 Vol.1, No.3



Title: Research note: the point of diminishing returns in heuristic search


Author: David L. Woodruff, Ulrike Ritzinger, Johan Oppen


Graduate School of Management, University of California, Davis, CA 95616, USA.
Institute of Computer Graphics and Algorithms, Vienna University of Technology, Favoritenstrasse 9-11, A-1040 Vienna, Austria.
Molde University College, P.O. Box 2110, 6402 Molde, Norway


Abstract: We provide a computable definition for the intuitive concept of the point of diminishing returns in a heuristic search. We also demonstrate that with proper scaling, the time point for a small instance can provide some guidance concerning the time point on larger instances. Computational results are presented for a range of problems and search methods.


Keywords: optimisation; runtime; time trace; search progression; search time; heuristic search; point of diminishing returns.


DOI: 10.1504/IJMHEUR.2011.041195


Int. J. of Metaheuristics, 2011 Vol.1, No.3, pp.222 - 231


Available online: 11 Jul 2011



Editors Full text accessAccess for SubscribersPurchase this articleComment on this article