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

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

Addresses: 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

International Journal of Metaheuristics, 2011 Vol.1 No.3, pp.222 - 231

Published online: 28 Feb 2015 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article