{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,6]],"date-time":"2025-11-06T00:52:57Z","timestamp":1762390377020},"publisher-location":"Berlin, Heidelberg","reference-count":35,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642042249"},{"type":"electronic","value":"9783642042256"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2009]]},"DOI":"10.1007\/978-3-642-04225-6_6","type":"book-chapter","created":{"date-parts":[[2009,10,4]],"date-time":"2009-10-04T01:17:38Z","timestamp":1254619058000},"page":"91-120","source":"Crossref","is-referenced-by-count":14,"title":["Computational Complexity of Ant\u00a0Colony\u00a0Optimization and Its Hybridization\u00a0with\u00a0Local\u00a0Search"],"prefix":"10.1007","author":[{"given":"Frank","family":"Neumann","sequence":"first","affiliation":[]},{"given":"Dirk","family":"Sudholt","sequence":"additional","affiliation":[]},{"given":"Carsten","family":"Witt","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"6_CR1","doi-asserted-by":"publisher","first-page":"1574","DOI":"10.1057\/palgrave.jors.2602308","volume":"58","author":"U. Aickelin","year":"2007","unstructured":"Aickelin, U., Burke, E.K., Li, J.: An estimation of distribution algorithm with intelligent local search for rule-based nurse rostering. Journal of the Operational Research Society\u00a058, 1574\u20131585 (2007)","journal-title":"Journal of the Operational Research Society"},{"issue":"3","key":"6_CR2","doi-asserted-by":"publisher","first-page":"88","DOI":"10.1016\/j.ipl.2007.08.013","volume":"105","author":"N. Attiratanasunthron","year":"2008","unstructured":"Attiratanasunthron, N., Fakcharoenphol, J.: A running time analysis of an ant colony optimization algorithm for shortest paths in directed acyclic graphs. Information Processing Letters\u00a0105(3), 88\u201392 (2008)","journal-title":"Information Processing Letters"},{"key":"6_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"156","DOI":"10.1007\/11839088_14","volume-title":"Ant Colony Optimization and Swarm Intelligence","author":"P. Balaprakash","year":"2006","unstructured":"Balaprakash, P., Birattari, M., St\u00fctzle, T., Dorigo, M.: Incremental local search in ant colony optimization: Why it fails for the quadratic assignment problem. In: Dorigo, M., Gambardella, L.M., Birattari, M., Martinoli, A., Poli, R., St\u00fctzle, T. (eds.) ANTS 2006. LNCS, vol.\u00a04150, pp. 156\u2013166. Springer, Heidelberg (2006)"},{"key":"6_CR4","volume-title":"Introduction to Algorithms","author":"T.H. Cormen","year":"2001","unstructured":"Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to Algorithms, 2nd edn. MIT Press, Cambridge (2001)","edition":"2"},{"key":"6_CR5","doi-asserted-by":"publisher","first-page":"501","DOI":"10.1109\/CEC.2007.4424512","volume-title":"Proceedings of the Congress of Evolutionary Computation (CEC 2007)","author":"B. Doerr","year":"2007","unstructured":"Doerr, B., Johannsen, D.: Refined runtime analysis of a basic ant colony optimization algorithm. In: Proceedings of the Congress of Evolutionary Computation (CEC 2007), pp. 501\u2013507. IEEE Computer Society Press, Los Alamitos (2007)"},{"key":"6_CR6","doi-asserted-by":"publisher","first-page":"33","DOI":"10.1145\/1276958.1276964","volume-title":"Proceedings of the Genetic and Evolutionary Computation Conference (GECCO 2007)","author":"B. Doerr","year":"2007","unstructured":"Doerr, B., Neumann, F., Sudholt, D., Witt, C.: On the runtime analysis of the 1-ANT ACO algorithm. In: Proceedings of the Genetic and Evolutionary Computation Conference (GECCO 2007), pp. 33\u201340. ACM Press, New York (2007)"},{"key":"6_CR7","doi-asserted-by":"publisher","first-page":"243","DOI":"10.1016\/j.tcs.2005.05.020","volume":"344","author":"M. Dorigo","year":"2005","unstructured":"Dorigo, M., Blum, C.: Ant colony optimization theory: A survey. Theoretical Computer Science\u00a0344, 243\u2013278 (2005)","journal-title":"Theoretical Computer Science"},{"key":"6_CR8","doi-asserted-by":"crossref","DOI":"10.7551\/mitpress\/1290.001.0001","volume-title":"Ant Colony Optimization","author":"M. Dorigo","year":"2004","unstructured":"Dorigo, M., St\u00fctzle, T.: Ant Colony Optimization. MIT Press, Cambridge (2004)"},{"key":"6_CR9","doi-asserted-by":"publisher","first-page":"51","DOI":"10.1016\/S0304-3975(01)00182-7","volume":"276","author":"S. Droste","year":"2002","unstructured":"Droste, S., Jansen, T., Wegener, I.: On the analysis of the (1+1) evolutionary algorithm. Theoretical Computer Science\u00a0276, 51\u201381 (2002)","journal-title":"Theoretical Computer Science"},{"issue":"4","key":"6_CR10","doi-asserted-by":"publisher","first-page":"525","DOI":"10.1007\/s00224-004-1177-z","volume":"39","author":"S. Droste","year":"2006","unstructured":"Droste, S., Jansen, T., Wegener, I.: Upper and lower bounds for randomized search heuristics in black-box optimization. Theory of Computing Systems\u00a039(4), 525\u2013544 (2006)","journal-title":"Theory of Computing Systems"},{"issue":"2","key":"6_CR11","doi-asserted-by":"publisher","first-page":"173","DOI":"10.1162\/evco.1999.7.2.173","volume":"7","author":"J. Garnier","year":"1999","unstructured":"Garnier, J., Kallel, L., Schoenauer, M.: Rigorous hitting times for binary mutations. Evolutionary Computation\u00a07(2), 173\u2013203 (1999)","journal-title":"Evolutionary Computation"},{"key":"6_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"415","DOI":"10.1007\/3-540-36494-3_37","volume-title":"STACS 2003","author":"O. Giel","year":"2003","unstructured":"Giel, O., Wegener, I.: Evolutionary algorithms and the maximum matching problem. In: Alt, H., Habib, M. (eds.) STACS 2003. LNCS, vol.\u00a02607, pp. 415\u2013426. Springer, Heidelberg (2003)"},{"key":"6_CR13","doi-asserted-by":"publisher","first-page":"873","DOI":"10.1016\/S0167-739X(00)00044-3","volume":"16","author":"W.J. Gutjahr","year":"2000","unstructured":"Gutjahr, W.J.: A graph-based ant system and its convergence. Future Generation Computer Systems\u00a016, 873\u2013888 (2000)","journal-title":"Future Generation Computer Systems"},{"key":"6_CR14","doi-asserted-by":"publisher","first-page":"545","DOI":"10.1017\/S0269964803174086","volume":"17","author":"W.J. Gutjahr","year":"2003","unstructured":"Gutjahr, W.J.: A generalized convergence result for the graph-based ant system metaheuristic. Probability in the Engineering and Informational Sciences\u00a017, 545\u2013569 (2003)","journal-title":"Probability in the Engineering and Informational Sciences"},{"key":"6_CR15","doi-asserted-by":"publisher","first-page":"59","DOI":"10.1007\/s11721-007-0001-1","volume":"1","author":"W.J. Gutjahr","year":"2007","unstructured":"Gutjahr, W.J.: Mathematical runtime analysis of ACO algorithms: Survey on an emerging issue. Swarm Intelligence\u00a01, 59\u201379 (2007)","journal-title":"Swarm Intelligence"},{"issue":"9","key":"6_CR16","doi-asserted-by":"publisher","first-page":"2711","DOI":"10.1016\/j.cor.2006.12.017","volume":"35","author":"W.J. Gutjahr","year":"2008","unstructured":"Gutjahr, W.J.: First steps to the runtime complexity analysis of ant colony optimization. Computers and Operations Research\u00a035(9), 2711\u20132727 (2008)","journal-title":"Computers and Operations Research"},{"key":"6_CR17","doi-asserted-by":"publisher","first-page":"409","DOI":"10.1007\/s11009-007-9047-1","volume":"10","author":"W.J. Gutjahr","year":"2008","unstructured":"Gutjahr, W.J., Sebastiani, G.: Runtime analysis of ant colony optimization with best-so-far reinforcement. Methodology and Computing in Applied Probability\u00a010, 409\u2013433 (2008)","journal-title":"Methodology and Computing in Applied Probability"},{"key":"6_CR18","series-title":"Studies in Fuzziness and Soft Computing","volume-title":"Recent Advances in Memetic Algorithms","year":"2004","unstructured":"Hart, W.E., Krasnogor, N., Smith, J.E. (eds.): Recent Advances in Memetic Algorithms. Studies in Fuzziness and Soft Computing, vol.\u00a0166. Springer, Heidelberg (2004)"},{"key":"6_CR19","unstructured":"Hoos, H.H., St\u00fctzle, T.: Stochastic Local Search: Foundations & Applications. Elsevier\/Morgan Kaufmann (2004)"},{"key":"6_CR20","doi-asserted-by":"publisher","first-page":"589","DOI":"10.1109\/4235.974841","volume":"5","author":"T. Jansen","year":"2001","unstructured":"Jansen, T., Wegener, I.: Evolutionary algorithms\u2014how to cope with plateaus of constant fitness and when to reject strings of the same fitness. IEEE Transactions on Evolutionary Computation\u00a05, 589\u2013599 (2001)","journal-title":"IEEE Transactions on Evolutionary Computation"},{"key":"6_CR21","volume-title":"Swarm Intelligence","author":"J. Kennedy","year":"2001","unstructured":"Kennedy, J., Eberhart, R.C., Shi, Y.: Swarm Intelligence. Morgan Kaufmann, San Francisco (2001)"},{"issue":"5","key":"6_CR22","doi-asserted-by":"publisher","first-page":"474","DOI":"10.1109\/TEVC.2005.850260","volume":"9","author":"N. Krasnogor","year":"2005","unstructured":"Krasnogor, N., Smith, J.: A tutorial for competent memetic algorithms: model, taxonomy, and design issues. IEEE Transactions on Evolutionary Computation\u00a09(5), 474\u2013488 (2005)","journal-title":"IEEE Transactions on Evolutionary Computation"},{"issue":"7","key":"6_CR23","doi-asserted-by":"publisher","first-page":"705","DOI":"10.1057\/palgrave.jors.2601771","volume":"55","author":"J. Levine","year":"2004","unstructured":"Levine, J., Ducatelle, F.: Ant colony optimisation and local search for bin packing and cutting stock problems. Journal of the Operational Research Society\u00a055(7), 705\u2013716 (2004)","journal-title":"Journal of the Operational Research Society"},{"key":"6_CR24","series-title":"International Series in Operations Research & Management Science","first-page":"321","volume-title":"Handbook of Metaheuristics","author":"H.R. Louren\u00e7o","year":"2002","unstructured":"Louren\u00e7o, H.R., Martin, O., St\u00fctzle, T.: Iterated local search. In: Handbook of Metaheuristics. International Series in Operations Research & Management Science, vol.\u00a057, pp. 321\u2013353. Kluwer Academic Publishers, Dordrecht (2002)"},{"issue":"3","key":"6_CR25","doi-asserted-by":"publisher","first-page":"235","DOI":"10.1162\/106365602760234090","volume":"10","author":"D. Merkle","year":"2002","unstructured":"Merkle, D., Middendorf, M.: Modelling the dynamics of Ant Colony Optimization algorithms. Evolutionary Computation\u00a010(3), 235\u2013262 (2002)","journal-title":"Evolutionary Computation"},{"issue":"1","key":"6_CR26","doi-asserted-by":"publisher","first-page":"32","DOI":"10.1016\/j.tcs.2006.11.002","volume":"378","author":"F. Neumann","year":"2007","unstructured":"Neumann, F., Wegener, I.: Randomized local search, evolutionary algorithms, and the minimum spanning tree problem. Theoretical Computer Science\u00a0378(1), 32\u201340 (2007)","journal-title":"Theoretical Computer Science"},{"key":"6_CR27","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"618","DOI":"10.1007\/11940128_62","volume-title":"Algorithms and Computation","author":"F. Neumann","year":"2006","unstructured":"Neumann, F., Witt, C.: Runtime analysis of a simple ant colony optimization algorithm. In: Asano, T. (ed.) ISAAC 2006. LNCS, vol.\u00a04288, pp. 618\u2013627. Springer, Heidelberg (2006)"},{"key":"6_CR28","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"153","DOI":"10.1007\/978-3-540-92695-5_12","volume-title":"Learning and Intelligent Optimization","author":"F. Neumann","year":"2008","unstructured":"Neumann, F., Witt, C.: Ant Colony Optimization and the minimum spanning tree problem. In: Maniezzo, V., Battiti, R., Watson, J.-P. (eds.) LION 2007 II. LNCS, vol.\u00a05313, pp. 153\u2013166. Springer, Heidelberg (2008)"},{"key":"6_CR29","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"132","DOI":"10.1007\/978-3-540-87527-7_12","volume-title":"Ant Colony Optimization and Swarm Intelligence","author":"F. Neumann","year":"2008","unstructured":"Neumann, F., Sudholt, D., Witt, C.: Rigorous analyses for the combination of ant colony optimization and local search. In: Dorigo, M., Birattari, M., Blum, C., Clerc, M., St\u00fctzle, T., Winfield, A.F.T. (eds.) ANTS 2008. LNCS, vol.\u00a05217, pp. 132\u2013143. Springer, Heidelberg (2008)"},{"key":"6_CR30","doi-asserted-by":"publisher","first-page":"35","DOI":"10.1007\/s11721-008-0023-3","volume":"3","author":"F. Neumann","year":"2009","unstructured":"Neumann, F., Sudholt, D., Witt, C.: Analysis of different MMAS ACO algorithms on unimodal functions and plateaus. Swarm Intelligence\u00a03, 35\u201368 (2009)","journal-title":"Swarm Intelligence"},{"key":"6_CR31","doi-asserted-by":"publisher","first-page":"889","DOI":"10.1016\/S0167-739X(00)00043-1","volume":"16","author":"T. St\u00fctzle","year":"2000","unstructured":"St\u00fctzle, T., Hoos, H.H.: MAX-MIN ant system. Journal of Future Generation Computer Systems\u00a016, 889\u2013914 (2000)","journal-title":"Journal of Future Generation Computer Systems"},{"key":"6_CR32","doi-asserted-by":"publisher","first-page":"787","DOI":"10.1145\/1389095.1389251","volume-title":"Proceedings of the Genetic and Evolutionary Computation Conference (GECCO 2008)","author":"D. Sudholt","year":"2008","unstructured":"Sudholt, D.: Memetic algorithms with variable-depth search to overcome local optima. In: Proceedings of the Genetic and Evolutionary Computation Conference (GECCO 2008), pp. 787\u2013794. ACM Press, New York (2008)"},{"key":"6_CR33","doi-asserted-by":"crossref","unstructured":"Sudholt, D.: The impact of parametrization in memetic evolutionary algorithms. Theoretical Computer Science (to appear, 2009)","DOI":"10.1016\/j.tcs.2009.03.003"},{"key":"6_CR34","doi-asserted-by":"publisher","first-page":"225","DOI":"10.1017\/S0963548304006650","volume":"14","author":"I. Wegener","year":"2005","unstructured":"Wegener, I., Witt, C.: On the optimization of monotone polynomials by simple randomized search heuristics. Combinatorics, Probability and Computing\u00a014, 225\u2013247 (2005)","journal-title":"Combinatorics, Probability and Computing"},{"key":"6_CR35","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"44","DOI":"10.1007\/978-3-540-31856-9_4","volume-title":"STACS 2005","author":"C. Witt","year":"2005","unstructured":"Witt, C.: Worst-case and average-case approximations by simple randomized search heuristics. In: Diekert, V., Durand, B. (eds.) STACS 2005. LNCS, vol.\u00a03404, pp. 44\u201356. Springer, Heidelberg (2005)"}],"container-title":["Studies in Computational Intelligence","Innovations in Swarm Intelligence"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-04225-6_6.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,30]],"date-time":"2021-04-30T10:58:26Z","timestamp":1619780306000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-04225-6_6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009]]},"ISBN":["9783642042249","9783642042256"],"references-count":35,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-04225-6_6","relation":{},"ISSN":["1860-949X","1860-9503"],"issn-type":[{"type":"print","value":"1860-949X"},{"type":"electronic","value":"1860-9503"}],"subject":[],"published":{"date-parts":[[2009]]}}}