Research ArticleOpen AccessGoogle Scholar indexed
On Cost Based Algorithm Selection for Problem Solving
Federal University of Rio de Janeiro, Alberto Luiz Coimbra Institute-Graduate School and Research in Engineering, Industrial Engineering Program, Rio de Janeiro RJ, Brazil
Federal University of Santa Catarina, Campus Araranguá, Araranguá SC, Brazil
Department of Biostatistics, University of Rochester Medical Center, Rochester NY, USA
Institute of Science and Tehcnology, Federal University of Sao Paulo, So Jos dos Campos SP, Brazil
- 1 Federal University of Rio de Janeiro, Alberto Luiz Coimbra Institute-Graduate School and Research in Engineering, Industrial Engineering Program, Rio de Janeiro RJ, Brazil
- 2 Federal University of Santa Catarina, Campus Araranguá, Araranguá SC, Brazil
- 3 Department of Biostatistics, University of Rochester Medical Center, Rochester NY, USA
- 4 Institute of Science and Tehcnology, Federal University of Sao Paulo, So Jos dos Campos SP, Brazil
American Journal of Operations Research·Volume 03 (2013)·Pages 431–438·Published 18 September 2013·DOI10.4236/ajor.2013.35041
Copy link · social · email
Abstract
This work proposes a novel framework that enables one to compare distinct iterative procedures with known rates of convergence, in terms of the computational effort to be employed to reach some prescribed vicinity of the optimal solution to a given problem of interest. An algorithm is introduced that decides between two competing algorithms, which algorithm makes the best use of the computational resources for some prescribed error. Several examples are presented that illustrate the trade-offs involved in such a choice and demonstrate that choosing an algorithm over another with a higher rate of convergence can be perfectly justifiable in terms of the overall computational effort.
KeywordsDecision AnalysisComputational EffortNumerical Analysis Optimization
- T. H. Cormen, C. Stein, R. L. Rivest and C. E. Leiserson, “Introduction to Algorithms,” 3rd Edition, MIT Press, Cambridge, 2009.
- J. Hartmanis and R. E. Stearns, “On the Computational Complexity of Algorithms,” Transactions of the American Mathematical Society, Vol. 117, No. 5, 1965, pp. 285-306. doi:10.1090/S0002-9947-1965-0170805-7
- J. Belanger, A. Pavan and J. Wang, “Reductions Do Not Preserve Fast Convergence Rates in Average Time,” Algorithmica, Vol. 23, No. 4, 1999, pp. 363-378.
- M. R. Garey and D. S. Johnson, “Computers and Intractability: A Guide to the Theory of NP-Completeness,” Freeman and Company, New York, 1979.
- D. B. Lloyd Trefethen, “Numerical Linear Algebra,” SIAM, Philadelphia, 1997. doi:10.1137/1.9780898719574
- J. W. Demmel, “Applied Numerical Linear Algebra,” SIAM, Philadelphia, 1997. doi:10.1137/1.9781611971446
- N. J. Higham, “Accuracy and Stability of Numerical Algorithms,” SIAM, Philadelphia, 2002. doi:10.1137/1.9780898718027
- W. Hackbusch, “Multi-Grid Methods and Applications,” 2nd Edition, Springer Series in Computational Mathematics, Springer-Verlag, Berlin, 2003.
- Y. Shapira, “Matrix-Based Multigrid: Theory and Applications,” 2nd Edition, Springer Publishing Company, New York, 2008. doi:10.1007/978-0-387-49765-5
- M. Mitchell, “Introduction to Genetic Algoritms,” MIT Press, Cambridge, 2008.
- C. Chow and J. N. Tsitsiklis, “An Optimal One-Way Multigrid Algorithm for Discrete-Time Stochastic Control,” IEEE Transactions on Automatic Control, Vol. 36, No. 8, 1991, pp. 898-914. doi:10.1109/9.133184
- J. Nocedal and S. Wright, “Numerical Optimization,” Springer, New York, 1999. doi:10.1007/b98874
- M. Hofri, “Analysis of Algorithms: Computational Methods and Mathematical Tools,” Oxford University Press, New York, 1995.