{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,6]],"date-time":"2025-07-06T15:40:10Z","timestamp":1751816410808,"version":"3.41.0"},"reference-count":37,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2018,8,25]],"date-time":"2018-08-25T00:00:00Z","timestamp":1535155200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["71471007"],"award-info":[{"award-number":["71471007"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100004731","name":"Natural Science Foundation of Zhejiang Province","doi-asserted-by":"publisher","award":["LY15F030021"],"award-info":[{"award-number":["LY15F030021"]}],"id":[{"id":"10.13039\/501100004731","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Cluster Comput"],"published-print":{"date-parts":[[2019,6]]},"DOI":"10.1007\/s10586-018-2838-z","type":"journal-article","created":{"date-parts":[[2018,8,25]],"date-time":"2018-08-25T08:53:46Z","timestamp":1535187226000},"page":"409-417","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Approximation guarantees of evolutionary optimization on the minimum crossing spanning tree problem"],"prefix":"10.1007","volume":"22","author":[{"given":"Jianping","family":"Zhang","sequence":"first","affiliation":[]},{"given":"Hong","family":"Zhou","sequence":"additional","affiliation":[]},{"given":"Huimin","family":"Gao","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2018,8,25]]},"reference":[{"key":"2838_CR1","doi-asserted-by":"crossref","unstructured":"Bil\u00f2, V., Flammini, M.: On the IP routing tables minimization with addresses reassignments. In: Proceedings, 18th International Parallel and Distributed Processing Symposium (IPDPS), pp. 19\u201326 (2004)","DOI":"10.1109\/IPDPS.2004.1302925"},{"key":"2838_CR2","doi-asserted-by":"crossref","unstructured":"Bil\u00f2, V., Goyal, V., Ravi, R., Singh, M.: On the crossing spanning tree problem. Proceedings. In: International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, pp. 51\u201360. Springer, Berlin (2004)","DOI":"10.1007\/978-3-540-27821-4_5"},{"key":"2838_CR3","unstructured":"F\u00fcrer, M., Raghavachari, B.: Approximating the minimum degree spanning tree to within one from the optimal degree. In: Proceedings of the 3rd Annual ACM-SIAM Symposium on Discrete Algorithms, ACM, pp. 317\u2013324 (1992)"},{"key":"2838_CR4","doi-asserted-by":"crossref","unstructured":"Witt, C.: Worst-case and average-case approximations by simple randomized search heuristics. In: Proceedings of the 22th Symposium on Theoretical Aspects of Computer Science Proceedings (STACS05). Lecture Notes on Computer Science, vol. 3404, pp. 44\u201356. Springer, Heidelberg (2005)","DOI":"10.1007\/978-3-540-31856-9_4"},{"issue":"1","key":"2838_CR5","doi-asserted-by":"publisher","first-page":"21","DOI":"10.1007\/s00453-014-9898-0","volume":"73","author":"Y Zhou","year":"2015","unstructured":"Zhou, Y., Zhang, J., Wang, Y.: Performance analysis of the (1\u00a0+\u00a01) evolutionary algorithm for the multiprocessor scheduling problem. Algorithmica 73(1), 21\u201341 (2015)","journal-title":"Algorithmica"},{"issue":"4","key":"2838_CR6","doi-asserted-by":"publisher","first-page":"543","DOI":"10.1162\/EVCO_a_00159","volume":"23","author":"T Friedrich","year":"2015","unstructured":"Friedrich, T., Neumann, F.: Maximizing submodular functions under Matroid constraints by evolutionary algorithms. Evolut. Comput. 23(4), 543\u2013558 (2015)","journal-title":"Evolut. Comput."},{"key":"2838_CR7","doi-asserted-by":"publisher","unstructured":"Xia, X., Lai, X., Yi, C.: The analysis of evolutionary optimization on the TSP(1,2) problem. Int. J. Comput. Sci. Eng. (2017). https:\/\/doi.org\/10.1504\/IJCSE.2016.10007955","DOI":"10.1504\/IJCSE.2016.10007955"},{"issue":"1","key":"2838_CR8","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1162\/evco.2009.17.1.3","volume":"17","author":"T Friedrich","year":"2009","unstructured":"Friedrich, T., He, J., Hebbinghaus, N., Neumann, F., Witt, C.: Analyses of simple hybrid algorithms for the vertex cover problem. Evolut. Comput. 17(1), 3\u201319 (2009)","journal-title":"Evolut. Comput."},{"key":"2838_CR9","doi-asserted-by":"publisher","first-page":"20","DOI":"10.1016\/j.artint.2012.01.001","volume":"180","author":"Y Yu","year":"2012","unstructured":"Yu, Y., Yao, X., Zhou, Z.H.: On the approximation ability of evolutionary optimizationwith application to minimum set cover. Artif. Intell. 180, 20\u201333 (2012)","journal-title":"Artif. Intell."},{"issue":"4","key":"2838_CR10","doi-asserted-by":"publisher","first-page":"595","DOI":"10.1162\/EVCO_a_00119","volume":"22","author":"AM Sutton","year":"2014","unstructured":"Sutton, A.M., Neumann, F., Nallaperuma, S.: Parameterized runtime analyses of evolutionary algorithms for the planar Euclidean traveling salesperson problem. Evolut. Comput. 22(4), 595\u2013628 (2014)","journal-title":"Evolut. Comput."},{"issue":"1","key":"2838_CR11","doi-asserted-by":"publisher","first-page":"26","DOI":"10.1049\/cje.2017.06.004","volume":"27","author":"X Xia","year":"2018","unstructured":"Xia, X., Zhou, Y.: Performance analysis of ACO on the quadratic assignment problem. Chin. J. Electron. 27(1), 26\u201334 (2018)","journal-title":"Chin. J. Electron."},{"issue":"6","key":"2838_CR12","doi-asserted-by":"publisher","first-page":"3611","DOI":"10.1166\/jctn.2016.5190","volume":"13","author":"X Xia","year":"2016","unstructured":"Xia, X., Zhang, G., Fan, D.: Performance analysis of evolutionary optimization on the minimum degree spanning tree problem. J. Comput. Theor. Nanosci. 13(6), 3611\u20133618 (2016)","journal-title":"J. Comput. Theor. Nanosci."},{"key":"2838_CR13","volume-title":"Computers and Intractibility: A Guide to the Theory of NP-Completeness","author":"MR Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractibility: A Guide to the Theory of NP-Completeness. W. H. Freeman and Company, New York (1979)"},{"issue":"2","key":"2838_CR14","doi-asserted-by":"publisher","first-page":"219","DOI":"10.1089\/cmb.1995.2.219","volume":"2","author":"DS Greenberg","year":"1995","unstructured":"Greenberg, D.S., Istrail, S.: Physical mapping by STS Hybridization: algorithmic strategies and the challenges of software evaluation. J. Comput. Biol. 2(2), 219\u2013273 (1995)","journal-title":"J. Comput. Biol."},{"key":"2838_CR15","unstructured":"Roh, P.: Minimum crossing problems on graphs. UWSpace. http:\/\/hdl.handle.net\/10012\/2658 (2007)"},{"issue":"3","key":"2838_CR16","doi-asserted-by":"publisher","first-page":"225","DOI":"10.1109\/TEVC.2002.807275","volume":"7","author":"GR Raidl","year":"2003","unstructured":"Raidl, G.R., Julstrom, B.A.: Edge sets: an effective evolutionary coding of spanning tree. IEEE Trans. Evolut. Comput. 7(3), 225\u2013239 (2003)","journal-title":"IEEE Trans. Evolut. Comput."},{"issue":"1\u20132","key":"2838_CR17","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\u00a0+\u00a01)-evolutionary algorithm. Theor. Comput. Sci. 276(1\u20132), 51\u201381 (2002)","journal-title":"Theor. Comput. Sci."},{"issue":"2","key":"2838_CR18","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 multiobjective evolutionary algorithms on pseudo-Boolean functions. IEEE Trans. Evolut. Comput. 8(2), 170\u2013182 (2004)","journal-title":"IEEE Trans. Evolut. Comput."},{"issue":"3","key":"2838_CR19","first-page":"591","volume":"13","author":"D Brockhoff","year":"2009","unstructured":"Brockhoff, D., Friedrich, T., Hebbinghaus, N., Klein, C., Neumann, F., Zitzler, E.: On the effects of adding objectives to plateau functions. IEEE Trans. Circuits Syst Video Technol. 13(3), 591\u2013603 (2009)","journal-title":"IEEE Trans. Circuits Syst Video Technol."},{"issue":"3","key":"2838_CR20","doi-asserted-by":"publisher","first-page":"305","DOI":"10.1007\/s11047-006-9004-x","volume":"5","author":"F Neumann","year":"2006","unstructured":"Neumann, F., Wegener, I.: Minimum spanning trees made easier via multi-objective optimization. Nat. Comput. 5(3), 305\u2013319 (2006)","journal-title":"Nat. Comput."},{"issue":"3","key":"2838_CR21","doi-asserted-by":"publisher","first-page":"1620","DOI":"10.1016\/j.ejor.2006.08.005","volume":"181","author":"F Neumann","year":"2007","unstructured":"Neumann, F.: Expected runtimes of a simple evolutionary algorithm for the multiobjective minimum spanning tree problem. Eur. J. Oper. Res. 181(3), 1620\u20131629 (2007)","journal-title":"Eur. J. Oper. Res."},{"issue":"4","key":"2838_CR22","doi-asserted-by":"publisher","first-page":"617","DOI":"10.1162\/EVCO_a_00003","volume":"18","author":"T Friedrich","year":"2010","unstructured":"Friedrich, T., He, J., Hebbinghaus, N., Neumann, F., Witt, C.: Approximating covering problems by randomized search heuristics using multi-objective models. Evolut. Comput. 18(4), 617\u2013633 (2010)","journal-title":"Evolut. Comput."},{"key":"2838_CR23","doi-asserted-by":"crossref","unstructured":"Neumann. F., Reichel, J.: Approximating minimum multicuts by evolutionary multi-objective algorithms. In: Proceedings of the 10th International Conference on Parallel Problem Solving from Nature X, PPSN 2008, LNCS 5199, Springer, Dortmund, pp. 72\u201381 (2008)","DOI":"10.1007\/978-3-540-87700-4_8"},{"key":"2838_CR24","doi-asserted-by":"crossref","unstructured":"Greiner, G.: Single- and multi-objective evolutionary algorithms for graph bisectioning. In: Proceedings of Foundation of Genetic Algorithms (FOGA 2009), ACM Press, pp. 29\u201338 (2009)","DOI":"10.1145\/1527125.1527131"},{"issue":"6","key":"2838_CR25","doi-asserted-by":"publisher","first-page":"860","DOI":"10.1109\/TEVC.2013.2291790","volume":"18","author":"X Lai","year":"2014","unstructured":"Lai, X., Zhou, Y., He, J., Zhang, J.: Performance analysis on evolutionary algorithms for the minimum label spanning tree problem. IEEE Trans. Evolut. Comput. 18(6), 860\u2013872 (2014)","journal-title":"IEEE Trans. Evolut. Comput."},{"key":"2838_CR26","series-title":"Lecture Notes in Computer Science","volume-title":"Evolutionary Computation in Combinatorial Optimization","author":"J He","year":"2015","unstructured":"He, J., Wang, Y., Zhoum, Y.: Analysis of solution quality of a multiobjective optimization-based evolutionary algorithm for Knapsack problem. In: Ochoa, G., Chicano, F. (eds.) Evolutionary Computation in Combinatorial Optimization. Lecture Notes in Computer Science, vol. 9026. Springer, Cham (2015)"},{"issue":"4","key":"2838_CR27","doi-asserted-by":"publisher","first-page":"323","DOI":"10.1023\/B:JMMA.0000049378.57591.c6","volume":"3","author":"MT Jensen","year":"2004","unstructured":"Jensen, M.T.: Helper-objectives: using multi-objective evolutionary algorithms for single-objective optimisation. J. Math. Modell. Algorithms 3(4), 323\u2013347 (2004)","journal-title":"J. Math. Modell. Algorithms"},{"key":"2838_CR28","doi-asserted-by":"publisher","first-page":"87","DOI":"10.1016\/j.ins.2017.10.038","volume":"426","author":"X Xia","year":"2018","unstructured":"Xia, X., Zhou, Y.: On the effectiveness of immune inspired mutation operators in some discrete optimization problems. Inform. Sci. 426, 87\u2013100 (2018)","journal-title":"Inform. Sci."},{"key":"2838_CR29","doi-asserted-by":"publisher","unstructured":"Xia, X., Tang, L., Peng, X.: When is the immune inspired B-Cell algorithm superior to the (1\u00a0+\u00a01) evolutionary algorithm. Int. J. High Perform. Comput. Network. (2017). https:\/\/doi.org\/10.1504\/IJHPCN.2016.10007954","DOI":"10.1504\/IJHPCN.2016.10007954"},{"key":"2838_CR30","doi-asserted-by":"crossref","unstructured":"Gupta, B.B., Agrawal, D.P., Yamaguchi, S.: Handbook of Research on Modern Cryptographic Solutions for Computer and Cyber Security (2016)","DOI":"10.4018\/978-1-5225-0105-3"},{"key":"2838_CR31","doi-asserted-by":"publisher","first-page":"506","DOI":"10.1016\/j.asoc.2017.09.028","volume":"66","author":"M Kim","year":"2017","unstructured":"Kim, M., Gupta, B.B., Rho, S.: Crowd sourcing based scientific issue tracking with topic analysis. Appl. Soft Comput. 66, 506\u2013511 (2017)","journal-title":"Appl. Soft Comput."},{"key":"2838_CR32","doi-asserted-by":"publisher","first-page":"349","DOI":"10.1016\/j.future.2017.09.082","volume":"82","author":"AP Plageras","year":"2018","unstructured":"Plageras, A.P., Stergiou, C., Psannis, K.E.: Efficient IoT-based sensor BIG data collectioncprocessing and analysis in smart buildings. Future Gener. Comput. Syst. 82, 349\u2013357 (2018)","journal-title":"Future Gener. Comput. Syst."},{"key":"2838_CR33","doi-asserted-by":"publisher","first-page":"5290","DOI":"10.1109\/ACCESS.2017.2763596","volume":"6","author":"Y Wang","year":"2018","unstructured":"Wang, Y., Jiang, F., Gupta, B.B.: Variable selection and optimization in rapid detection of soybean straw biomass based on CARS. IEEE Access. 6, 5290\u20135299 (2018)","journal-title":"IEEE Access."},{"key":"2838_CR34","doi-asserted-by":"publisher","first-page":"95","DOI":"10.1016\/j.ins.2018.01.041","volume":"438","author":"H Wang","year":"2018","unstructured":"Wang, H., Wang, W., Cui, Z.: A new dynamic firefly algorithm for demand estimation of water resources. Inform. Sci. 438, 95\u2013106 (2018)","journal-title":"Inform. Sci."},{"key":"2838_CR35","doi-asserted-by":"publisher","first-page":"17756","DOI":"10.1109\/ACCESS.2017.2779154","volume":"6","author":"X Xia","year":"2018","unstructured":"Xia, X., Peng, X., Deng, L.: Performance analysis of evolutionary optimization for the bank account location problem. IEEE Access. 6, 17756\u201317767 (2018)","journal-title":"IEEE Access."},{"issue":"9","key":"2838_CR36","doi-asserted-by":"publisher","first-page":"3537","DOI":"10.1007\/s00500-015-1710-9","volume":"20","author":"P He","year":"2016","unstructured":"He, P., Deng, Z., Wang, H.: Model approach to grammatical evolution: theory and case study. Soft Comput. 20(9), 3537\u20133548 (2016)","journal-title":"Soft Comput."},{"issue":"18","key":"2838_CR37","doi-asserted-by":"publisher","first-page":"5413","DOI":"10.1007\/s00500-016-2130-1","volume":"21","author":"P He","year":"2017","unstructured":"He, P., Deng, Z., Gao, C.: Model approach to grammatical evolution: deep-structured analyzing of model and representation. Soft Comput. 21(18), 5413\u20135423 (2017)","journal-title":"Soft Comput."}],"container-title":["Cluster Computing"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10586-018-2838-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10586-018-2838-z\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10586-018-2838-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,7,6]],"date-time":"2025-07-06T15:16:49Z","timestamp":1751815009000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10586-018-2838-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,8,25]]},"references-count":37,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2019,6]]}},"alternative-id":["2838"],"URL":"https:\/\/doi.org\/10.1007\/s10586-018-2838-z","relation":{},"ISSN":["1386-7857","1573-7543"],"issn-type":[{"type":"print","value":"1386-7857"},{"type":"electronic","value":"1573-7543"}],"subject":[],"published":{"date-parts":[[2018,8,25]]},"assertion":[{"value":"10 January 2018","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"16 April 2018","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"10 August 2018","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"25 August 2018","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Compliance with ethical standards"}},{"value":"The authors declare that they have no conflict of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}},{"value":"All procedures performed in studies involving human participants were in accordance with the ethical standards of the institutional and\/or national research committee and with the 1964 Helsinki Declaration and its later amendments or comparable ethical standards.","order":3,"name":"Ethics","group":{"name":"EthicsHeading","label":"Ethical standards"}},{"value":"This article does not contain any studies with animals performed by any of the authors.","order":4,"name":"Ethics","group":{"name":"EthicsHeading","label":"Human and animal rights statement"}},{"value":"Informed consent was obtained from all individual participants included in the study.","order":5,"name":"Ethics","group":{"name":"EthicsHeading","label":"Informed consent"}}]}}