{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,21]],"date-time":"2025-11-21T12:00:23Z","timestamp":1763726423140,"version":"3.38.0"},"publisher-location":"Berlin, Heidelberg","reference-count":38,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540272373"},{"type":"electronic","value":"9783540320357"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2005]]},"DOI":"10.1007\/11513575_7","type":"book-chapter","created":{"date-parts":[[2010,9,25]],"date-time":"2010-09-25T18:44:24Z","timestamp":1285440264000},"page":"112-131","source":"Crossref","is-referenced-by-count":13,"title":["Running Time Analysis of a Multiobjective Evolutionary Algorithm on Simple and Hard Problems"],"prefix":"10.1007","author":[{"given":"Rajeev","family":"Kumar","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Nilanjan","family":"Banerjee","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"7_CR1","volume-title":"Computers and Interactability: A Guide to the Theory of NPCompleteness","author":"M.R. Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Interactability: A Guide to the Theory of NPCompleteness. Freeman, San Francisco (1979)"},{"key":"7_CR2","volume-title":"Approximation Algorithms for NP-Hard Problems","author":"D. Hochbaum","year":"1997","unstructured":"Hochbaum, D.: Approximation Algorithms for NP-Hard Problems. PWS, Boston (1997)"},{"key":"7_CR3","doi-asserted-by":"publisher","first-page":"257","DOI":"10.1109\/4235.797969","volume":"3","author":"E. Zitzler","year":"1999","unstructured":"Zitzler, E., Thiele, L.: Multiobjective evolutionary algorithms: a comparative case study and the strength pareto approach. IEEE Trans. Evolutionary Computation\u00a03, 257\u2013271 (1999)","journal-title":"IEEE Trans. Evolutionary Computation"},{"key":"7_CR4","doi-asserted-by":"crossref","unstructured":"Knowles, J.D., Corne, D.W.: A Comparison of Encodings and Algorithms forMultiobjective Minimum Spanning Tree Problems. In: Proc. Congress on Evolutionary Computation (CEC 2001), vol.\u00a01, pp. 544\u2013551 (2001)","DOI":"10.1109\/CEC.2001.934439"},{"key":"7_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"494","DOI":"10.1007\/978-3-540-30474-6_52","volume-title":"High Performance Computing - HiPC 2004","author":"R. Kumar","year":"2004","unstructured":"Kumar, R., Singh, P.K., Chakrabarti, P.P.: Improved quality of solutions for multiobjective spanning tree problem using evolutionary algorithm. In: Boug\u00e9, L., Prasanna, V.K. (eds.) HiPC 2004. LNCS, vol.\u00a03296, pp. 494\u2013503. Springer, Heidelberg (2004)"},{"key":"7_CR6","doi-asserted-by":"publisher","first-page":"822","DOI":"10.1109\/72.712155","volume":"9","author":"R. Kumar","year":"1998","unstructured":"Kumar, R., Rockett, P.I.: Multiobjective genetic algorithm partitioning for hierarchical learning of high-dimensional pattern spaces: A learning-follows-decomposition strategy. IEEE Trans. Neural Networks\u00a09, 822\u2013830 (1998)","journal-title":"IEEE Trans. Neural Networks"},{"key":"7_CR7","unstructured":"Kumar, R.: Codebook design for vector quantization using multiobjective genetic algorithms. In: Proc. PPSN\/SAB Workshop on Multiobjective Problem Solving from Nature (2000)"},{"key":"7_CR8","doi-asserted-by":"crossref","unstructured":"Kumar, R., Parida, P.P., Gupta, M.: Topological design of communication networks using multiobjective genetic optimization. In: Proc. Congress Evolutionary Computation (CEC 2002), pp. 425\u2013430 (2002)","DOI":"10.1109\/CEC.2002.1006272"},{"key":"7_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"2179","DOI":"10.1007\/3-540-45110-2_113","volume-title":"Genetic and Evolutionary Computation - GECCO 2003","author":"R. Kumar","year":"2003","unstructured":"Kumar, R., Banerjee, N.: Multicriteria network design using evolutionary algorithm. In: Cant\u00fa-Paz, E., Foster, J.A., Deb, K., Davis, L., Roy, R., O\u2019Reilly, U.-M., Beyer, H.-G., Kendall, G., Wilson, S.W., Harman, M., Wegener, J., Dasgupta, D., Potter, M.A., Schultz, A., Dowsland, K.A., Jonoska, N., Miller, J., Standish, R.K. (eds.) GECCO 2003. LNCS, vol.\u00a02723, pp. 2179\u20132190. Springer, Heidelberg (2003)"},{"key":"7_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"44","DOI":"10.1007\/3-540-45712-7_5","volume-title":"Parallel Problem Solving from Nature - PPSN VII","author":"M. Laumanns","year":"2002","unstructured":"Laumanns, M., Thiele, L., Zitzler, E., Welzl, E., Deb, K.: Running time analysis of multiobjective evolutionary algorithms on a discrete optimization problem. In: Guerv\u00f3s, J.J.M., Adamidis, P.A., Beyer, H.-G., Fern\u00e1ndez-Villaca\u00f1as, J.-L., Schwefel, H.-P. (eds.) PPSN 2002. LNCS, vol.\u00a02439, pp. 44\u201353. Springer, Heidelberg (2002)"},{"key":"7_CR11","doi-asserted-by":"publisher","first-page":"170","DOI":"10.1109\/TEVC.2004.823470","volume":"8","author":"M. Laumanns","year":"2004","unstructured":"Laumanns, M., Thiele, L., Zitzler, E.: Running time analysis of evolutionary algorithms on pseudo-boolean functions. IEEE Trans. Evolutionary Computation\u00a08, 170\u2013182 (2004)","journal-title":"IEEE Trans. Evolutionary Computation"},{"key":"7_CR12","doi-asserted-by":"publisher","first-page":"37","DOI":"10.1023\/B:NACO.0000023415.22052.55","volume":"3","author":"M. Laumanns","year":"2004","unstructured":"Laumanns, M., Thiele, L., Zitzler, E.: Running time analysis of evolutionary algorithms on a simplified multiobjective knapsack problem. Natural Computing\u00a03, 37\u201351 (2004)","journal-title":"Natural Computing"},{"key":"7_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"13","DOI":"10.1007\/BFb0056845","volume-title":"Parallel Problem Solving from Nature - PPSN V","author":"S. Droste","year":"1998","unstructured":"Droste, S., Jansen, T., Wegener, I.: On the Optimization of Unimodal Functions with the (1+1) Evolutionary Algorithm. In: Eiben, A.E., B\u00e4ck, T., Schoenauer, M., Schwefel, H.-P. (eds.) PPSN 1998. LNCS, vol.\u00a01498, pp. 13\u201322. Springer, Heidelberg (1998)"},{"key":"7_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1068","DOI":"10.1007\/3-540-45061-0_82","volume-title":"Automata, Languages and Programming","author":"J. Jagersk\u00fcpper","year":"2003","unstructured":"Jagersk\u00fcpper, J.: Analysis of simple evolutionary algorithm for minimization in euclidean spaces. In: Baeten, J.C.M., Lenstra, J.K., Parrow, J., Woeginger, G.J. (eds.) ICALP 2003. LNCS, vol.\u00a02719, pp. 1068\u20131079. Springer, Heidelberg (2003)"},{"key":"7_CR15","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":"7_CR16","doi-asserted-by":"publisher","first-page":"167","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, 167\u2013203 (1999)","journal-title":"Evolutionary Computation"},{"key":"7_CR17","doi-asserted-by":"publisher","first-page":"207","DOI":"10.1162\/evco.1996.4.2.195","volume":"4","author":"G. Rudolph","year":"1996","unstructured":"Rudolph, G.: How mutation and selection solve long path problems in polynomial expected time. Evolutionary Computation\u00a04, 207\u2013211 (1996)","journal-title":"Evolutionary Computation"},{"key":"7_CR18","unstructured":"Wegener, I., Witt, C.: On the analysis of a simple evolutionary algorithm on quadratic pseudo-boolean functions. J. Discrete Algorithms (2002)"},{"key":"7_CR19","doi-asserted-by":"publisher","first-page":"47","DOI":"10.1007\/s00453-002-0940-2","volume":"34","author":"T. Jansen","year":"2002","unstructured":"Jansen, T., Wegener, I.: The analysis of evolutionary algorithms: a proof that crossover really can help. Algorithmica\u00a034, 47\u201366 (2002)","journal-title":"Algorithmica"},{"key":"7_CR20","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4757-5184-0","volume-title":"Evolutionary Algorithms for Solving Multiojective Problems","author":"C.A.C. Coello","year":"2002","unstructured":"Coello, C.A.C., Veldhuizen, D.A.V., Lamont, G.B.: Evolutionary Algorithms for Solving Multiojective Problems. Kluwer, Boston (2002)"},{"key":"7_CR21","volume-title":"Multiobjective Optimization Using Evolutionary Algorithms","author":"K. Deb","year":"2001","unstructured":"Deb, K.: Multiobjective Optimization Using Evolutionary Algorithms. Wiley, Chichester (2001)"},{"key":"7_CR22","volume-title":"Convergence Properties of Evolutionary Algorithms","author":"G. Rudolph","year":"1997","unstructured":"Rudolph, G.: Convergence Properties of Evolutionary Algorithms. Verlag Dr. Kovac\u0306, Hamburg (1997)"},{"key":"7_CR23","doi-asserted-by":"crossref","unstructured":"Rudolph, G.: Evolutionary search for minimal elements in partially ordered finite sets. In: Proc. Annual Conference on Evolutionary Programming, pp. 345\u2013353 (1998)","DOI":"10.1007\/BFb0040787"},{"key":"7_CR24","doi-asserted-by":"crossref","unstructured":"Rudolph, G., Agapie, A.: Convergence properties of some multiobjective evolutionary algorithms. In: Proc. Congress on Evolutionary Computation, pp. 1010\u20131016 (2000)","DOI":"10.1109\/CEC.2000.870756"},{"key":"7_CR25","unstructured":"Giel, O.: Runtime analysis for a simple multiobjective evolutionary algorithm. Tech-Report, Dept. Computer Science, Univ. Dortmund, Germany (2003)"},{"key":"7_CR26","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"355","DOI":"10.1007\/3-540-36970-8_25","volume-title":"Evolutionary Multi-Criterion Optimization","author":"D. Thierens","year":"2003","unstructured":"Thierens, D.: Convergence time analysis for the multi-objective counting ones problem. In: Fonseca, C.M., Fleming, P.J., Zitzler, E., Deb, K., Thiele, L. (eds.) EMO 2003. LNCS, vol.\u00a02632, pp. 355\u2013364. Springer, Heidelberg (2003)"},{"key":"7_CR27","unstructured":"Asho, I.: Interactive Knapsacks: Theory and Applications. Ph.D. Thesis, Tech Report No.: A- 2002-13, Department of Computer and Information Sciences, University of Tampere (2002)"},{"key":"7_CR28","doi-asserted-by":"publisher","first-page":"100","DOI":"10.1016\/0377-2217(84)90053-5","volume":"15","author":"A. Frieze","year":"1984","unstructured":"Frieze, A., Clarke, M.: Approximation algorithms form-dimensional 0-1 knapsack problem: Worst case and probabilistic analysis. European J. Operations Research\u00a015, 100\u2013109 (1984)","journal-title":"European J. Operations Research"},{"key":"7_CR29","doi-asserted-by":"publisher","first-page":"1603","DOI":"10.1287\/mnsc.48.12.1603.445","volume":"48","author":"T. Erlebach","year":"2002","unstructured":"Erlebach, T., Kellerer, H., Pferschy, U.: Approximating Multiobjective Knapsack Problems. Management Science\u00a048, 1603\u20131612 (2002)","journal-title":"Management Science"},{"key":"7_CR30","doi-asserted-by":"publisher","first-page":"463","DOI":"10.1145\/321906.321909","volume":"22","author":"O.H. Ibarra","year":"1984","unstructured":"Ibarra, O.H., Kim, C.E.: Fast approximation algorithms for the knapsack and sum of subset problem. J. ACM\u00a022, 463\u2013468 (1984)","journal-title":"J. ACM"},{"key":"7_CR31","doi-asserted-by":"publisher","first-page":"101","DOI":"10.1016\/S0304-3975(02)00137-8","volume":"287","author":"H.G. Beyer","year":"2002","unstructured":"Beyer, H.G., Schwefel, H.P., Wegener, I.: How to Analyse Evolutionary Algorithms? Theoretical Computer Science\u00a0287, 101\u2013130 (2002)","journal-title":"Theoretical Computer Science"},{"key":"7_CR32","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"54","DOI":"10.1007\/3-540-45712-7_6","volume-title":"Parallel Problem Solving from Nature - PPSN VII","author":"J. Scharnow","year":"2002","unstructured":"Scharnow, J., Tinnefeld, K., Wegener, I.: Fitness landscapes based on sorting and shortest path problems. In: Guerv\u00f3s, J.J.M., Adamidis, P.A., Beyer, H.-G., Fern\u00e1ndez-Villaca\u00f1as, J.-L., Schwefel, H.-P. (eds.) PPSN 2002. LNCS, vol.\u00a02439, pp. 54\u201363. Springer, Heidelberg (2002)"},{"key":"7_CR33","unstructured":"Droste, S., Jansen, T., Tinnefeld, K., Wegener, I.: A new framework for the valuation of algorithms for black-box optimization. In: Proc. Foundations of Genetic Algorithms Workshop (FOGA VII), pp. 197\u2013214 (2002)"},{"key":"7_CR34","doi-asserted-by":"crossref","unstructured":"Deb, K., et al.: A Fast Non-Dominated Sorting Genetic Algorithm for Multiobjective Optimization: NSGA-II. In: Proc. Parallel Problem Solving from Nature (PPSN-VI). LNCS, pp. 849\u2013858 (2000)","DOI":"10.1007\/3-540-45356-3_83"},{"key":"7_CR35","doi-asserted-by":"publisher","first-page":"149","DOI":"10.1162\/106365600568167","volume":"8","author":"J.D. Knowles","year":"2000","unstructured":"Knowles, J.D., Corne, D.W.: Approximating the Non-Dominated Front Using the Pareto Achieved Evolution Strategy. Evolutionary Computation\u00a08, 149\u2013172 (2000)","journal-title":"Evolutionary Computation"},{"key":"7_CR36","doi-asserted-by":"publisher","first-page":"283","DOI":"10.1162\/106365602760234117","volume":"10","author":"R. Kumar","year":"2002","unstructured":"Kumar, R., Rockett, P.I.: Improved Sampling of the Pareto-front in Multiobjective Genetic Optimization by Steady-State Evolution: A Pareto Converging Genetic Algorithm. Evolutionary Computation\u00a010, 283\u2013314 (2002)","journal-title":"Evolutionary Computation"},{"key":"7_CR37","unstructured":"Zitzler, E., Laumanns, M., Thiele, L.: SPEA2: Improving the Strength Pareto Evolutionary Algorithm. In: Proc. Evolutionary Methods for Design, Optimization and Control with Applications to Industrial Problems, EUROGEN (2001)"},{"key":"7_CR38","doi-asserted-by":"publisher","first-page":"117","DOI":"10.1109\/TEVC.2003.810758","volume":"7","author":"E. Zitzler","year":"2003","unstructured":"Zitzler, E., Thiele, L., Laumanns, M., Fonseca, C.M., da Fonseca, V.G.: Performance assessment of multiobjective optimizers: An analysis and review. IEEE Trans. Evolutionary Computation\u00a07, 117\u2013132 (2003)","journal-title":"IEEE Trans. Evolutionary Computation"}],"container-title":["Lecture Notes in Computer Science","Foundations of Genetic Algorithms"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11513575_7","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,2,26]],"date-time":"2025-02-26T02:16:56Z","timestamp":1740536216000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11513575_7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005]]},"ISBN":["9783540272373","9783540320357"],"references-count":38,"URL":"https:\/\/doi.org\/10.1007\/11513575_7","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2005]]}}}