{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,27]],"date-time":"2026-05-27T15:32:03Z","timestamp":1779895923166,"version":"3.53.1"},"reference-count":16,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2007,11,28]],"date-time":"2007-11-28T00:00:00Z","timestamp":1196208000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by-nc\/2.0"},{"start":{"date-parts":[[2007,11,28]],"date-time":"2007-11-28T00:00:00Z","timestamp":1196208000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by-nc\/2.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2009,6]]},"DOI":"10.1007\/s00453-007-9134-2","type":"journal-article","created":{"date-parts":[[2007,11,27]],"date-time":"2007-11-27T15:35:46Z","timestamp":1196177746000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":67,"title":["Runtime Analysis of a Simple Ant Colony Optimization Algorithm"],"prefix":"10.1007","volume":"54","author":[{"given":"Frank","family":"Neumann","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Carsten","family":"Witt","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2007,11,28]]},"reference":[{"key":"9134_CR1","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. Theor. Comput. Sci. 344, 243\u2013278 (2005)","journal-title":"Theor. Comput. Sci."},{"key":"9134_CR2","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, Cambridge (2004)"},{"key":"9134_CR3","unstructured":"Dorigo, M., Maniezzo, V., Colorni, A.: The ant system: An autocatalytic optimizing process. Tech. Rep. 91-016 Revised, Politecnico di Milano, Italy (1991)"},{"key":"9134_CR4","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. Theor. Comput. Sci. 276, 51\u201381 (2002)","journal-title":"Theor. Comput. Sci."},{"key":"9134_CR5","volume-title":"An Introduction to Probability Theory and Its Applications","author":"W. Feller","year":"1968","unstructured":"Feller, W.: An Introduction to Probability Theory and Its Applications, 3rd edn., vol.\u00a01. Wiley, New York (1968)","edition":"3"},{"key":"9134_CR6","volume-title":"An Introduction to Probability Theory and Its Applications","author":"W. Feller","year":"1971","unstructured":"Feller, W.: An Introduction to Probability Theory and Its Applications, 2nd edn., vol.\u00a02. Wiley, New York (1971)","edition":"2"},{"key":"9134_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"415","DOI":"10.1007\/3-540-36494-3_37","volume-title":"Proceedings of the 20th Annual Symposium on Theoretical Aspects of Computer Science","author":"O. Giel","year":"2003","unstructured":"Giel, O., Wegener, I.: Evolutionary algorithms and the maximum matching problem. In: Proceedings of the 20th Annual Symposium on Theoretical Aspects of Computer Science. Lecture Notes in Computer Science, vol. 2607, pp. 415\u2013426. Springer, Berlin (2003)"},{"issue":"1","key":"9134_CR8","doi-asserted-by":"publisher","first-page":"182","DOI":"10.1214\/aop\/1176996461","volume":"3","author":"L.J. Gleser","year":"1975","unstructured":"Gleser, L.J.: On the distribution of the number of successes in independent trials. Ann. Probab. 3(1), 182\u2013188 (1975)","journal-title":"Ann. Probab."},{"key":"9134_CR9","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. Probab. Eng. Inf. Sci. 17, 545\u2013569 (2003)","journal-title":"Probab. Eng. Inf. Sci."},{"key":"9134_CR10","doi-asserted-by":"publisher","first-page":"105","DOI":"10.1007\/s11009-006-7291-4","volume":"8","author":"W.J. Gutjahr","year":"2006","unstructured":"Gutjahr, W.J.: On the finite-time dynamics of ant colony optimization. Methodol. Comput. Appl. Probab. 8, 105\u2013133 (2006)","journal-title":"Methodol. Comput. Appl. Probab."},{"issue":"1\u20133","key":"9134_CR11","doi-asserted-by":"publisher","first-page":"155","DOI":"10.1016\/S0166-218X(97)00133-9","volume":"82","author":"M. Jerrum","year":"1998","unstructured":"Jerrum, M., Sorkin, G.B.: The Metropolis algorithm for graph bisection. Discrete Appl. Math. 82(1\u20133), 155\u2013175 (1998)","journal-title":"Discrete Appl. Math."},{"key":"9134_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"713","DOI":"10.1007\/978-3-540-24854-5_73","volume-title":"Proceedings of the Genetic and Evolutionary Computation Conference (GECCO \u201904)","author":"F. Neumann","year":"2004","unstructured":"Neumann, F., Wegener, I.: Randomized local search, evolutionary algorithms, and the minimum spanning tree problem. In: Proceedings of the Genetic and Evolutionary Computation Conference (GECCO \u201904). Lecture Notes in Computer Science, vol. 3102, pp. 713\u2013724. Springer, Berlin (2004)"},{"key":"9134_CR13","doi-asserted-by":"publisher","first-page":"438","DOI":"10.1145\/100216.100274","volume-title":"Proceedings of the 22nd Annual ACM Symposium on Theory of Computing (STOC \u201990)","author":"C.H. Papadimitriou","year":"1990","unstructured":"Papadimitriou, C.H., Sch\u00e4ffer, A.A., Yannakakis, M.: On the complexity of local search. In: Proceedings of the 22nd Annual ACM Symposium on Theory of Computing (STOC \u201990), pp. 438\u2013445. ACM Press, Cambridge (1990)"},{"key":"9134_CR14","unstructured":"Scheideler, C.: Probabilistic methods for coordination problems. HNI-Verlagsschriftenreihe 78. Habilitation Thesis, University of Paderborn. Available at http:\/\/www14.in.tum.de\/personen\/scheideler\/index.html.en (2000)"},{"key":"9134_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"589","DOI":"10.1007\/11523468_48","volume-title":"Proceedings of the 32nd International Colloquium on Automata, Languages and Programming (ICALP \u201905)","author":"I. Wegener","year":"2005","unstructured":"Wegener, I.: Simulated annealing beats Metropolis in combinatorial optimization. In: Proceedings of the 32nd International Colloquium on Automata, Languages and Programming (ICALP \u201905). Lecture Notes in Computer Science, vol. 3580, pp. 589\u2013601. Springer, Berlin (2005)"},{"key":"9134_CR16","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":"Proceedings of the 22nd Annual Symposium on Theoretical Aspects of Computer Science (STACS\u00a0\u201905)","author":"C. Witt","year":"2005","unstructured":"Witt, C.: Worst-case and average-case approximations by simple randomized search heuristics. In: Proceedings of the 22nd Annual Symposium on Theoretical Aspects of Computer Science (STACS\u00a0\u201905). Lecture Notes in Computer Science, vol. 3404, pp. 44\u201356. Springer, Berlin (2005)"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-007-9134-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-007-9134-2\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-007-9134-2.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-007-9134-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,8,31]],"date-time":"2021-08-31T19:27:45Z","timestamp":1630438065000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-007-9134-2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007,11,28]]},"references-count":16,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2009,6]]}},"alternative-id":["9134"],"URL":"https:\/\/doi.org\/10.1007\/s00453-007-9134-2","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2007,11,28]]},"assertion":[{"value":"22 January 2007","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"20 November 2007","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"28 November 2007","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"243"}}