{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,27]],"date-time":"2026-01-27T22:44:41Z","timestamp":1769553881438,"version":"3.49.0"},"publisher-location":"Berlin, Heidelberg","reference-count":15,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540249986","type":"print"},{"value":"9783540318569","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2005]]},"DOI":"10.1007\/978-3-540-31856-9_4","type":"book-chapter","created":{"date-parts":[[2010,3,2]],"date-time":"2010-03-02T18:06:19Z","timestamp":1267553179000},"page":"44-56","source":"Crossref","is-referenced-by-count":98,"title":["Worst-Case and Average-Case Approximations by Simple Randomized Search Heuristics"],"prefix":"10.1007","author":[{"given":"Carsten","family":"Witt","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"4_CR1","doi-asserted-by":"crossref","unstructured":"Beier, R., V\u00f6cking, B.: Random knapsack in expected polynomial time. In: Proc. of 35th STOC, pp. 232\u2013241 (2003)","DOI":"10.1145\/780542.780578"},{"key":"4_CR2","doi-asserted-by":"crossref","unstructured":"Spielman, D.A., Teng, S.H.: Smoothed analysis: Why the simplex algorithm usually takes polynomial time. In: Proc. of 33rd STOC, pp. 296\u2013305 (2001)","DOI":"10.1145\/380752.380813"},{"key":"4_CR3","volume-title":"Approximation Algorithms for NP-Hard Problems","year":"1997","unstructured":"Hochbaum, D.S. (ed.): Approximation Algorithms for NP-Hard Problems. Wadsworth Publishing Company, Belmont (1997)"},{"key":"4_CR4","doi-asserted-by":"publisher","first-page":"1087","DOI":"10.1126\/science.220.4598.671","volume":"220","author":"S. Kirkpatrick","year":"1983","unstructured":"Kirkpatrick, S., Gelatt, C.D., Vecchi, M.P.: Optimization by simulated annealing. Science\u00a0220, 1087\u20131092 (1983)","journal-title":"Science"},{"key":"4_CR5","doi-asserted-by":"crossref","unstructured":"Baeck, T., Fogel, D.B., Michalewicz, Z. (eds.): Handbook of Evolutionary Computation. Institute of Physics Publishing (1997)","DOI":"10.1887\/0750308958"},{"key":"4_CR6","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"},{"key":"4_CR7","doi-asserted-by":"crossref","unstructured":"Wegener, I., Witt, C.: On the optimization of monotone polynomials by simple randomized search heuristics. Combinatorics, Probability and Computing (2005) (in press)","DOI":"10.1017\/S0963548304006650"},{"key":"4_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"761","DOI":"10.1007\/978-3-540-24854-5_77","volume-title":"Genetic and Evolutionary Computation \u2013 GECCO 2004","author":"C. Witt","year":"2004","unstructured":"Witt, C.: An analysis of the (\u03bc+1)\u00a0EA on simple pseudo-boolean functions. In: Deb, K., et al. (eds.) GECCO 2004. LNCS, vol.\u00a03102, pp. 761\u2013773. Springer, Heidelberg (2004)"},{"key":"4_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","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":"4_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"713","DOI":"10.1007\/978-3-540-24854-5_73","volume-title":"Genetic and Evolutionary Computation \u2013 GECCO 2004","author":"F. Neumann","year":"2004","unstructured":"Neumann, F., Wegener, I.: Randomized local search, evolutionary algorithms, and the minimum spanning tree problem. In: Deb, K., et al. (eds.) GECCO 2004. LNCS, vol.\u00a03102, pp. 713\u2013724. Springer, Heidelberg (2004)"},{"key":"4_CR11","doi-asserted-by":"publisher","first-page":"187","DOI":"10.1016\/0166-218X(86)90060-0","volume":"14","author":"J.B.G. Frenk","year":"1986","unstructured":"Frenk, J.B.G., Rinnooy Kan, A.H.G.: The rate of convergence to optimality of the LPT rule. Discrete Applied Mathematics\u00a014, 187\u2013197 (1986)","journal-title":"Discrete Applied Mathematics"},{"key":"4_CR12","first-page":"15","volume-title":"Scheduling Theory and its Applications","author":"J..E.G. Coffman","year":"1995","unstructured":"Coffman, J.E.G., Whitt, W.: Recent asymptotic results in the probabilistic analysis of schedule makespans. In: Chr\u00e8tienne, P., Coffman Jr., E.G., Lenstra, J.K., Liu, Z. (eds.) Scheduling Theory and its Applications, pp. 15\u201331. Wiley, Chichester (1995)"},{"key":"4_CR13","first-page":"263","volume":"17","author":"R.L. Graham","year":"1969","unstructured":"Graham, R.L.: Bounds on multiprocessing timing anomalies. SIAM Journal on Applied Mathematics\u00a017, 263\u2013269 (1969)","journal-title":"SIAM Journal on Applied Mathematics"},{"key":"4_CR14","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511814075","volume-title":"Randomized Algorithms","author":"R. Motwani","year":"1995","unstructured":"Motwani, R., Raghavan, P.: Randomized Algorithms. Cambridge University Press, Cambridge (1995)"},{"key":"4_CR15","doi-asserted-by":"publisher","DOI":"10.1002\/0471722162","volume-title":"Order Statistics","author":"H.A. David","year":"2003","unstructured":"David, H.A., Nagaraja, H.N.: Order Statistics, 3rd edn. Wiley, Chichester (2003)","edition":"3"}],"container-title":["Lecture Notes in Computer Science","STACS 2005"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-31856-9_4.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,19]],"date-time":"2020-11-19T04:29:50Z","timestamp":1605760190000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-31856-9_4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005]]},"ISBN":["9783540249986","9783540318569"],"references-count":15,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-31856-9_4","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2005]]}}}