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.
Int. J. of Metaheuristics, 2011 Vol.1, No.3, pp.222 - 231
Available online: 11 Jul 2011