{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T07:26:53Z","timestamp":1740122813727,"version":"3.37.3"},"reference-count":38,"publisher":"Springer Science and Business Media LLC","issue":"1-2","license":[{"start":{"date-parts":[[2023,11,13]],"date-time":"2023-11-13T00:00:00Z","timestamp":1699833600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2023,11,13]],"date-time":"2023-11-13T00:00:00Z","timestamp":1699833600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"funder":[{"DOI":"10.13039\/501100001809","name":"NSFC","doi-asserted-by":"crossref","award":["61872159","62076108"],"award-info":[{"award-number":["61872159","62076108"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Heuristics"],"published-print":{"date-parts":[[2024,4]]},"DOI":"10.1007\/s10732-023-09521-y","type":"journal-article","created":{"date-parts":[[2023,11,13]],"date-time":"2023-11-13T18:01:58Z","timestamp":1699898518000},"page":"43-65","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["DSLS: a simple and efficient local search algorithm for the maximum bisection problem"],"prefix":"10.1007","volume":"30","author":[{"given":"Xinliang","family":"Tian","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Dantong","family":"Ouyang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Huisi","family":"Zhou","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Rui","family":"Sun","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8263-4194","authenticated-orcid":false,"given":"Liming","family":"Zhang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2023,11,13]]},"reference":[{"issue":"3","key":"9521_CR1","doi-asserted-by":"publisher","first-page":"506","DOI":"10.1007\/BF02510238","volume":"37","author":"C Ashcraft","year":"1997","unstructured":"Ashcraft, C., Liu, J.: Using domain decomposition to find graph bisectors. BIT Numer. Math. 37(3), 506\u2013534 (1997)","journal-title":"BIT Numer. Math."},{"issue":"1","key":"9521_CR2","first-page":"2","volume":"13","author":"P Austrin","year":"2016","unstructured":"Austrin, P., Benabbas, S., Georgiou, K.: Better balance by being biased: a 0.8776-approximation for max bisection. ACM Trans. Algorithms 13(1), 2\u20131227 (2016)","journal-title":"ACM Trans. Algorithms"},{"issue":"3","key":"9521_CR3","doi-asserted-by":"publisher","first-page":"493","DOI":"10.1287\/opre.36.3.493","volume":"36","author":"F Barahona","year":"1988","unstructured":"Barahona, F., Gr\u00f6tschel, M., J\u00fcnger, M., Reinelt, G.: An application of combinatorial optimization to statistical physics and circuit layout design. Oper. Res. 36(3), 493\u2013513 (1988)","journal-title":"Oper. Res."},{"issue":"3","key":"9521_CR4","doi-asserted-by":"publisher","first-page":"1162","DOI":"10.1016\/j.engappai.2012.09.001","volume":"26","author":"U Benlic","year":"2013","unstructured":"Benlic, U., Hao, J.: Breakout local search for the max-cutproblem. Eng. Appl. Artif. Intell. 26(3), 1162\u20131173 (2013)","journal-title":"Eng. Appl. Artif. Intell."},{"key":"9521_CR5","doi-asserted-by":"publisher","first-page":"243","DOI":"10.1007\/BF02614373","volume":"77","author":"L Brunetta","year":"1997","unstructured":"Brunetta, L., Conforti, M., Rinaldi, G.: A branch-and-cut algorithm for the equicut problem. Math. Program. 77, 243\u2013263 (1997)","journal-title":"Math. Program."},{"key":"9521_CR6","doi-asserted-by":"crossref","unstructured":"Cai, S., Zhang, X.: Deep cooperation of CDCL and local search for SAT. In: Theory and Applications of Satisfiability Testing\u2014SAT 2021\u201424th International Conference, pp. 64\u201381 (2021)","DOI":"10.1007\/978-3-030-80223-3_6"},{"issue":"1","key":"9521_CR7","doi-asserted-by":"publisher","first-page":"67","DOI":"10.1109\/TCAD.1987.1270247","volume":"6","author":"KC Chang","year":"1987","unstructured":"Chang, K.C., Du, D.H.: Efficient algorithms for layer assignment problem. IEEE Trans. Comput. Aided Des. Integr. Circuits Syst. 6(1), 67\u201378 (1987)","journal-title":"IEEE Trans. Comput. Aided Des. Integr. Circuits Syst."},{"issue":"11","key":"9521_CR8","doi-asserted-by":"publisher","first-page":"1253","DOI":"10.1109\/12.736440","volume":"47","author":"J Cho","year":"1998","unstructured":"Cho, J., Raje, S., Sarrafzadeh, M.: Fast approximation algorithms on maxcut, k-coloring, and k-color ordering for VLSI applications. IEEE Trans. Comput. 47(11), 1253\u20131266 (1998)","journal-title":"IEEE Trans. Comput."},{"issue":"2","key":"9521_CR9","doi-asserted-by":"publisher","first-page":"417","DOI":"10.1007\/s10107-014-0811-z","volume":"153","author":"D Delling","year":"2015","unstructured":"Delling, D., Fleischman, D., Goldberg, A.V., Razenshteyn, I.P., Werneck, R.F.: An exact combinatorial algorithm for minimum graph bisection. Math. Program. 153(2), 417\u2013458 (2015)","journal-title":"Math. Program."},{"key":"9521_CR10","doi-asserted-by":"crossref","unstructured":"Ding, C.H.Q., He, X., Zha, H., Gu, M., Simon, H.D.: A min-max cut algorithm for graph partitioning and data clustering. In: Proceedings of the 2001 IEEE International Conference on Data Mining, pp. 107\u2013114 (2001)","DOI":"10.1109\/ICDM.2001.989507"},{"key":"9521_CR11","doi-asserted-by":"publisher","first-page":"125","DOI":"10.1016\/j.jcss.2021.02.002","volume":"119","author":"E Eiben","year":"2021","unstructured":"Eiben, E., Lokshtanov, D., Mouawad, A.E.: Bisection of bounded treewidth graphs by convolutions. J. Comput. Syst. Sci. 119, 125\u2013132 (2021)","journal-title":"J. Comput. Syst. Sci."},{"issue":"4","key":"9521_CR12","doi-asserted-by":"publisher","first-page":"522","DOI":"10.1109\/TSMC.2016.2606400","volume":"48","author":"W Fang","year":"2018","unstructured":"Fang, W., Yao, X., Zhao, X., Yin, J., Xiong, N.: A stochastic control approach to maximize profit on service provisioning for mobile cloudlet platforms. IEEE Trans. Syst. Man Cybern. Syst. 48(4), 522\u2013534 (2018)","journal-title":"IEEE Trans. Syst. Man Cybern. Syst."},{"issue":"6","key":"9521_CR13","doi-asserted-by":"publisher","first-page":"1033","DOI":"10.1080\/1055678021000090033","volume":"17","author":"P Festa","year":"2002","unstructured":"Festa, P., Pardalos, P.M., Resende, M.G.C., Ribeiro, C.C.: Randomized heuristics for the max-cut problem. Optim. Methods Softw. 17(6), 1033\u20131058 (2002)","journal-title":"Optim. Methods Softw."},{"issue":"1","key":"9521_CR14","doi-asserted-by":"publisher","first-page":"67","DOI":"10.1007\/BF02523688","volume":"18","author":"AM Frieze","year":"1997","unstructured":"Frieze, A.M., Jerrum, M.: Improved approximation algorithms for MAX k-cut and MAX BISECTION. Algorithmica 18(1), 67\u201381 (1997)","journal-title":"Algorithmica"},{"issue":"6","key":"9521_CR15","doi-asserted-by":"publisher","first-page":"1115","DOI":"10.1145\/227683.227684","volume":"42","author":"MX Goemans","year":"1995","unstructured":"Goemans, M.X., Williamson, D.P.: Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. J. ACM 42(6), 1115\u20131145 (1995)","journal-title":"J. ACM"},{"key":"9521_CR16","doi-asserted-by":"publisher","first-page":"38","DOI":"10.1016\/j.tcs.2021.04.023","volume":"873","author":"T Hanaka","year":"2021","unstructured":"Hanaka, T., Kobayashi, Y., Sone, T.: A (probably) optimal algorithm for bisection on bounded-treewidth graphs. Theor. Comput. Sci. 873, 38\u201346 (2021)","journal-title":"Theor. Comput. Sci."},{"issue":"2","key":"9521_CR17","doi-asserted-by":"publisher","first-page":"452","DOI":"10.1137\/0916028","volume":"16","author":"B Hendrickson","year":"1995","unstructured":"Hendrickson, B., Leland, R.W.: An improved spectral graph partitioning algorithm for mapping parallel computations. SIAM J. Sci. Comput. 16(2), 452\u2013469 (1995)","journal-title":"SIAM J. Sci. Comput."},{"key":"9521_CR18","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.ins.2018.09.063","volume":"476","author":"A Herran","year":"2019","unstructured":"Herran, A., Colmenar, J.M., Duarte, A.: A variable neighborhood search approach for the vertex bisection problem. Inf. Sci. 476, 1\u201318 (2019)","journal-title":"Inf. Sci."},{"issue":"1","key":"9521_CR19","doi-asserted-by":"publisher","first-page":"110","DOI":"10.1137\/S009753970139567X","volume":"35","author":"K Jansen","year":"2005","unstructured":"Jansen, K., Karpinski, M., Lingas, A., Seidel, E.: Polynomial time approximation schemes for MAX-BISECTION on planar and geometric graphs. SIAM J. Comput. 35(1), 110\u2013119 (2005)","journal-title":"SIAM J. Comput."},{"issue":"9","key":"9521_CR20","doi-asserted-by":"publisher","first-page":"1321","DOI":"10.1093\/comjnl\/bxz063","volume":"63","author":"Z Lei","year":"2020","unstructured":"Lei, Z., Cai, S.: NuDist: an efficient local search algorithm for (weighted) partial MaxSAT. Comput. J. 63(9), 1321\u20131337 (2020)","journal-title":"Comput. J."},{"issue":"8","key":"9521_CR21","doi-asserted-by":"publisher","first-page":"1792","DOI":"10.3390\/s17081792","volume":"17","author":"H Li","year":"2017","unstructured":"Li, H., Liu, J., Liu, R.W., Xiong, N., Wu, K., Kim, T.: A dimensionality reduction-based multi-step clustering method for robust vessel trajectory analysis. Sensors 17(8), 1792 (2017)","journal-title":"Sensors"},{"issue":"6","key":"9521_CR22","doi-asserted-by":"publisher","first-page":"1365","DOI":"10.1109\/TC.2013.7","volume":"63","author":"G Lin","year":"2014","unstructured":"Lin, G., Zhu, W.: An efficient memetic algorithm for the max-bisection problem. IEEE Trans. Comput. 63(6), 1365\u20131376 (2014)","journal-title":"IEEE Trans. Comput."},{"issue":"7","key":"9521_CR23","doi-asserted-by":"publisher","first-page":"4254","DOI":"10.1109\/TII.2019.2905659","volume":"15","author":"B Lin","year":"2019","unstructured":"Lin, B., Zhu, F., Zhang, J., Chen, J., Chen, X., Xiong, N.N., Mauri, J.L.: A time-driven data placement strategy for a scientific workflow combining edge computing and cloud computing. IEEE Trans. Ind. Inform. 15(7), 4254\u20134265 (2019)","journal-title":"IEEE Trans. Ind. Inform."},{"issue":"1","key":"9521_CR24","doi-asserted-by":"publisher","first-page":"413","DOI":"10.1016\/j.cam.2007.08.018","volume":"220","author":"A Ling","year":"2008","unstructured":"Ling, A., Xu, C., Tang, L.: A modified VNS metaheuristic for max-bisection problems. J. Comput. Appl. Math. 220(1), 413\u2013421 (2008)","journal-title":"J. Comput. Appl. Math."},{"key":"9521_CR25","doi-asserted-by":"publisher","first-page":"78","DOI":"10.1016\/j.cor.2016.12.012","volume":"81","author":"F Ma","year":"2017","unstructured":"Ma, F., Hao, J., Wang, Y.: An effective iterated tabu search for the maximum bisection problem. Comput. Oper. Res. 81, 78\u201389 (2017)","journal-title":"Comput. Oper. Res."},{"issue":"2","key":"9521_CR26","doi-asserted-by":"publisher","first-page":"117","DOI":"10.1007\/BF02592948","volume":"39","author":"KG Murty","year":"1987","unstructured":"Murty, K.G., Kabadi, S.N.: Some NP-complete problems in quadratic and nonlinear programming. Math. Program. 39(2), 117\u2013129 (1987)","journal-title":"Math. Program."},{"key":"9521_CR27","doi-asserted-by":"crossref","unstructured":"Qu, Y., Xiong, N.: RFH: A resilient, fault-tolerant and high-efficient replication algorithm for distributed cloud storage. In: 41st International Conference on Parallel Processing, pp. 520\u2013529 (2012)","DOI":"10.1109\/ICPP.2012.3"},{"key":"9521_CR28","doi-asserted-by":"crossref","unstructured":"Raghavendra, P., Tan, N.: Approximating CSPs with global cardinality constraints using SDP hierarchies. In: Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 373\u2013387 (2012)","DOI":"10.1137\/1.9781611973099.33"},{"issue":"4","key":"9521_CR29","doi-asserted-by":"publisher","first-page":"563","DOI":"10.1007\/s10559-012-9435-6","volume":"48","author":"VP Shylo","year":"2012","unstructured":"Shylo, V.P., Shylo, O.V., Roschyn, V.A.: Solving weighted max-cut problem by global equilibrium search. Cybern. Syst. Anal. 48(4), 563\u2013567 (2012)","journal-title":"Cybern. Syst. Anal."},{"issue":"1","key":"9521_CR30","doi-asserted-by":"publisher","first-page":"16","DOI":"10.1007\/s10559-015-9692-2","volume":"51","author":"VP Shylo","year":"2015","unstructured":"Shylo, V.P., Glover, F., Sergienko, I.V.: Teams of global equilibrium search algorithms for solving the weighted maximum cut problem in parallel. Cybern. Syst. Anal. 51(1), 16\u201324 (2015)","journal-title":"Cybern. Syst. Anal."},{"key":"9521_CR31","doi-asserted-by":"crossref","unstructured":"Wang, Y., Cai, S., Chen, J., Yin, M.: A fast local search algorithm for minimum weight dominating set problem on massive graphs. In: Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence, pp. 1514\u20131522 (2018)","DOI":"10.24963\/ijcai.2018\/210"},{"key":"9521_CR32","doi-asserted-by":"crossref","unstructured":"Wang, Y., Cai, S., Pan, S., Li, X., Yin, M.: Reduction and local search for weighted graph coloring problem. In: The Thirty-Fourth AAAI Conference on Artificial Intelligence, pp. 2433\u20132441 (2020a)","DOI":"10.1609\/aaai.v34i03.5624"},{"key":"9521_CR33","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2019.103230","volume":"280","author":"Y Wang","year":"2020","unstructured":"Wang, Y., Cai, S., Chen, J., Yin, M.: SCCWalk: an efficient local search algorithm and its improvements for maximum weight clique problem. Artif. Intell. 280, 103230 (2020b)","journal-title":"Artif. Intell."},{"issue":"1","key":"9521_CR34","doi-asserted-by":"publisher","first-page":"166","DOI":"10.1016\/j.cor.2012.06.001","volume":"40","author":"Q Wu","year":"2013","unstructured":"Wu, Q., Hao, J.: Memetic search for the max-bisection problem. Comput. Oper. Res. 40(1), 166\u2013179 (2013)","journal-title":"Comput. Oper. Res."},{"issue":"1","key":"9521_CR35","doi-asserted-by":"publisher","first-page":"248","DOI":"10.3390\/s150100248","volume":"15","author":"M Wu","year":"2015","unstructured":"Wu, M., Tan, L., Xiong, N.: A structure fidelity approach for big data collection in wireless sensor networks. Sensors 15(1), 248\u2013273 (2015)","journal-title":"Sensors"},{"issue":"13","key":"9521_CR36","doi-asserted-by":"publisher","first-page":"3718","DOI":"10.1016\/j.cam.2011.01.015","volume":"235","author":"F Xu","year":"2011","unstructured":"Xu, F., Ma, X., Chen, B.: A new Lagrangian net algorithm for solving max-bisection problems. J. Comput. Appl. Math. 235(13), 3718\u20133723 (2011)","journal-title":"J. Comput. Appl. Math."},{"issue":"1","key":"9521_CR37","doi-asserted-by":"publisher","first-page":"101","DOI":"10.1007\/PL00011415","volume":"90","author":"Y Ye","year":"2001","unstructured":"Ye, Y.: A .699-approximation algorithm for max-bisection. Math. Program. 90(1), 101\u2013111 (2001)","journal-title":"Math. Program."},{"issue":"2","key":"9521_CR38","doi-asserted-by":"publisher","first-page":"151","DOI":"10.3934\/naco.2015.5.151","volume":"5","author":"W Zhu","year":"2015","unstructured":"Zhu, W., Liu, Y., Lin, G.: Speeding up a memetic algorithm for the max-bisection problem. Numer. Algebra Control Optim. 5(2), 151\u2013168 (2015)","journal-title":"Numer. Algebra Control Optim."}],"container-title":["Journal of Heuristics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10732-023-09521-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10732-023-09521-y\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10732-023-09521-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,11,1]],"date-time":"2024-11-01T22:48:32Z","timestamp":1730501312000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10732-023-09521-y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,11,13]]},"references-count":38,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2024,4]]}},"alternative-id":["9521"],"URL":"https:\/\/doi.org\/10.1007\/s10732-023-09521-y","relation":{},"ISSN":["1381-1231","1572-9397"],"issn-type":[{"type":"print","value":"1381-1231"},{"type":"electronic","value":"1572-9397"}],"subject":[],"published":{"date-parts":[[2023,11,13]]},"assertion":[{"value":"21 December 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"5 October 2023","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"12 October 2023","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"13 November 2023","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The author has no affiliation with any organization with a direct or indirect financial interest in the subject matter discussed in the manuscript.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}