{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,31]],"date-time":"2025-10-31T07:41:07Z","timestamp":1761896467144,"version":"3.37.3"},"reference-count":35,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2017,3,3]],"date-time":"2017-03-03T00:00:00Z","timestamp":1488499200000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100000038","name":"Natural Sciences and Engineering Research Council of Canada","doi-asserted-by":"publisher","award":["312125","418250"],"award-info":[{"award-number":["312125","418250"]}],"id":[{"id":"10.13039\/501100000038","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Ann Oper Res"],"published-print":{"date-parts":[[2018,6]]},"DOI":"10.1007\/s10479-017-2448-9","type":"journal-article","created":{"date-parts":[[2017,3,3]],"date-time":"2017-03-03T09:14:10Z","timestamp":1488532450000},"page":"5-27","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":6,"title":["Computational study of valid inequalities for the maximum k-cut problem"],"prefix":"10.1007","volume":"265","author":[{"given":"Vilmar Jeft\u00e9","family":"Rodrigues de Sousa","sequence":"first","affiliation":[]},{"given":"Miguel F.","family":"Anjos","sequence":"additional","affiliation":[]},{"given":"S\u00e9bastien","family":"Le Digabel","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2017,3,3]]},"reference":[{"key":"2448_CR1","doi-asserted-by":"crossref","first-page":"355","DOI":"10.1007\/978-3-642-38189-8_15","volume-title":"Facets of combinatorial optimization","author":"MF Anjos","year":"2013","unstructured":"Anjos, M. F., Ghaddar, B., Hupp, L., Liers, F., & Wiegele, A. (2013). Solving \n                        $$k$$\n                        \n                            \n                                k\n                            \n                        \n                    -way graph partitioning problems to optimality: The impact of semidefinite relaxations and the bundle method. In M. J\u00fcnger & G. Reinelt (Eds.), Facets of combinatorial optimization (pp. 355\u2013386). Berlin: Springer."},{"issue":"3","key":"2448_CR2","doi-asserted-by":"crossref","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. (1988). An application of combinatorial optimization to statistical physics and circuit layout design. Operations Research, 36(3), 493\u2013513.","journal-title":"Operations Research"},{"issue":"1","key":"2448_CR3","doi-asserted-by":"crossref","first-page":"87","DOI":"10.1007\/BF01581239","volume":"59","author":"S Chopra","year":"1993","unstructured":"Chopra, S., & Rao, M. R. (1993). The partition problem. Mathematical Programming, 59(1), 87\u2013115.","journal-title":"Mathematical Programming"},{"issue":"1","key":"2448_CR4","doi-asserted-by":"crossref","first-page":"27","DOI":"10.1016\/0166-218X(93)E0175-X","volume":"61","author":"S Chopra","year":"1995","unstructured":"Chopra, S., & Rao, M. R. (1995). Facets of the k-partition polytope. Discrete Applied Mathematics, 61(1), 27\u201348.","journal-title":"Discrete Applied Mathematics"},{"issue":"3","key":"2448_CR5","doi-asserted-by":"crossref","first-page":"289","DOI":"10.1002\/rsa.20096","volume":"28","author":"A Coja-Oghlan","year":"2006","unstructured":"Coja-Oghlan, A., Moore, C., & Sanwalani, V. (2006). Max \n                        $$k$$\n                        \n                            \n                                k\n                            \n                        \n                    -cut and approximating the chromatic number of random graphs. Random Structures and Algorithms, 28(3), 289\u2013322.","journal-title":"Random Structures and Algorithms"},{"issue":"5","key":"2448_CR6","doi-asserted-by":"crossref","first-page":"828","DOI":"10.1109\/TCAD.1987.1270326","volume":"6","author":"W-M Dai","year":"1987","unstructured":"Dai, W.-M., & Kuh, E. S. (1987). Simultaneous floor planning and global routing for hierarchical building-block layout. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 6(5), 828\u2013837.","journal-title":"IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems"},{"issue":"3","key":"2448_CR7","doi-asserted-by":"crossref","first-page":"267","DOI":"10.1023\/B:JOCO.0000038911.67280.3f","volume":"8","author":"E Klerk de","year":"2004","unstructured":"de Klerk, E., Pasechnik, D. V., & Warners, J. P. (2004). On approximate graph colouring and max-\n                        $$k$$\n                        \n                            \n                                k\n                            \n                        \n                    -cut algorithms based on the \n                        $$\\theta $$\n                        \n                            \n                                \u03b8\n                            \n                        \n                    -function. Journal of Combinatorial Optimization, 8(3), 267\u2013294.","journal-title":"Journal of Combinatorial Optimization"},{"issue":"4","key":"2448_CR8","doi-asserted-by":"crossref","first-page":"981","DOI":"10.1287\/moor.17.4.981","volume":"17","author":"M Deza","year":"1992","unstructured":"Deza, M., Gr\u00f6tschel, M., & Laurent, M. (1992). Clique-web facets for multicut polytopes. Mathematics of Operations Research, 17(4), 981\u20131000.","journal-title":"Mathematics of Operations Research"},{"key":"2448_CR9","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-04295-9","volume-title":"Geometry of cuts and metrics","author":"MM Deza","year":"1997","unstructured":"Deza, M. M., & Laurent, M. (1997). Geometry of cuts and metrics (1st ed.). Berlin: Springer.","edition":"1"},{"issue":"2","key":"2448_CR10","doi-asserted-by":"crossref","first-page":"201","DOI":"10.1007\/s101070100263","volume":"91","author":"ED Dolan","year":"2002","unstructured":"Dolan, E. D., & Mor\u00e9, J. J. (2002). Benchmarking optimization software with performance profiles. Mathematical Programming, 91(2), 201\u2013213.","journal-title":"Mathematical Programming"},{"key":"2448_CR11","unstructured":"Eisenbl\u00e4tter, A. (2002). The semidefinite relaxation of the k-partition polytope is strong, volume 2337 of lecture notes in computer science (pp. 273\u2013290). Berlin: Springer."},{"key":"2448_CR12","unstructured":"Fairbrother, J., & Letchford, N. (2016). Projection results for the k-partition problem. Technical Report Optimization Online 5370, Department of Management Science, Lancaster University, UK."},{"issue":"2","key":"2448_CR13","doi-asserted-by":"crossref","first-page":"109","DOI":"10.1007\/BF01096763","volume":"6","author":"TA Feo","year":"1995","unstructured":"Feo, T. A., & Resende, M. G. C. (1995). Greedy randomized adaptive search procedures. Journal of Global Optimization, 6(2), 109\u2013133.","journal-title":"Journal of Global Optimization"},{"issue":"1","key":"2448_CR14","doi-asserted-by":"crossref","first-page":"67","DOI":"10.1007\/BF02523688","volume":"18","author":"A Frieze","year":"1997","unstructured":"Frieze, A., & Jerrum, M. (1997). Improved approximation algorithms for maxk-cut and max bisection. Algorithmica, 18(1), 67\u201381.","journal-title":"Algorithmica"},{"issue":"1","key":"2448_CR15","doi-asserted-by":"crossref","first-page":"65","DOI":"10.1007\/s10107-007-0139-z","volume":"115","author":"D Gaur","year":"2008","unstructured":"Gaur, D., Krishnamurti, R., & Kohli, R. (2008). The capacitated max \n                        $$k$$\n                        \n                            \n                                k\n                            \n                        \n                    -cut problem. Mathematical Programming, 115(1), 65\u201372.","journal-title":"Mathematical Programming"},{"issue":"2","key":"2448_CR16","doi-asserted-by":"crossref","first-page":"359","DOI":"10.1287\/moor.10.2.359","volume":"10","author":"AMH Gerards","year":"1985","unstructured":"Gerards, A. M. H. (1985). Testing the odd bicycle wheel inequalities for the bipartite subgraph polytope. Mathematics of Operations Research, 10(2), 359\u2013360.","journal-title":"Mathematics of Operations Research"},{"issue":"1","key":"2448_CR17","doi-asserted-by":"crossref","first-page":"155","DOI":"10.1007\/s10479-008-0481-4","volume":"188","author":"B Ghaddar","year":"2011","unstructured":"Ghaddar, B., Anjos, M. F., & Liers, F. (2011). A branch-and-cut algorithm based on semidefinite programming for the minimum \n                        $$k$$\n                        \n                            \n                                k\n                            \n                        \n                    -partition problem. Annals of Operations Research, 188(1), 155\u2013174.","journal-title":"Annals of Operations Research"},{"issue":"6","key":"2448_CR18","doi-asserted-by":"crossref","first-page":"1115","DOI":"10.1145\/227683.227684","volume":"42","author":"MX Goemans","year":"1995","unstructured":"Goemans, M. X., & Williamson, D. P. (1995). Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. Journal of the ACM, 42(6), 1115\u20131145.","journal-title":"Journal of the ACM"},{"issue":"1","key":"2448_CR19","first-page":"61","volume":"143","author":"N Krislock","year":"2012","unstructured":"Krislock, N., Malick, J., & Roupin, F. (2012). Improved semidefinite bounding procedure for solving max-cut problems to optimality. Mathematical Programming, 143(1), 61\u201386.","journal-title":"Mathematical Programming"},{"key":"2448_CR20","first-page":"47","volume-title":"Computing Exact Ground states of hard Ising spin glass problems by branch-and-cut","author":"F Liers","year":"2005","unstructured":"Liers, F., J\u00fcnger, M., Reinelt, G., & Rinaldi, G. (2005). Computing Exact Ground states of hard Ising spin glass problems by branch-and-cut (pp. 47\u201369). Hoboken: Wiley."},{"key":"2448_CR21","doi-asserted-by":"publisher","unstructured":"Ma, F., & Hao, J.-K. (2017). A multiple search operator heuristic for the max-k-cut problem. Annals of Operations Research, 248(1), 365\u2013403. doi:\n                        10.1007\/s10479-016-2234-0\n                        \n                    .","DOI":"10.1007\/s10479-016-2234-0"},{"issue":"7","key":"2448_CR22","doi-asserted-by":"crossref","first-page":"683","DOI":"10.1002\/nav.10084","volume":"50","author":"JE Mitchell","year":"2003","unstructured":"Mitchell, J. E. (2003). Realignment in the national football league: Did they do it right? Naval Research Logistics, 50(7), 683\u2013701.","journal-title":"Naval Research Logistics"},{"issue":"1","key":"2448_CR23","doi-asserted-by":"crossref","first-page":"172","DOI":"10.1137\/080724083","volume":"20","author":"JJ Mor\u00e9","year":"2009","unstructured":"Mor\u00e9, J. J., & Wild, S. M. (2009). Benchmarking derivative-free optimization algorithms. SIAM Journal on Optimization, 20(1), 172\u2013191.","journal-title":"SIAM Journal on Optimization"},{"key":"2448_CR24","unstructured":"Mosek ApS. (2015).mosek. \n                        http:\/\/www.mosek.com\n                        \n                    ."},{"key":"2448_CR25","doi-asserted-by":"crossref","first-page":"462","DOI":"10.1016\/j.laa.2016.04.019","volume":"504","author":"V Nikiforov","year":"2016","unstructured":"Nikiforov, V. (2016). Max k-cut and the smallest eigenvalue. Linear Algebra and its Applications, 504, 462\u2013467.","journal-title":"Linear Algebra and its Applications"},{"key":"2448_CR26","volume-title":"Handbook of semidefinite, conic and polynomial optimization: Theory, algorithms, software and applications, international series in operations research and management science","author":"L Palagi","year":"2011","unstructured":"Palagi, L., Piccialli, V., Rendl, F., Rinaldi, G., & Wiegele, A. (2011). computational approaches to max-cut. In M. F. Anjos & J. B. Lasserre (Eds.), Handbook of semidefinite, conic and polynomial optimization: Theory, algorithms, software and applications, international series in operations research and management science. New York: Springer."},{"issue":"3","key":"2448_CR27","doi-asserted-by":"crossref","first-page":"425","DOI":"10.1016\/0022-0000(91)90023-X","volume":"43","author":"CH Papadimitriou","year":"1991","unstructured":"Papadimitriou, C. H., & Yannakakis, M. (1991). Optimization, approximation, and complexity classes. Journal of Computer and System Sciences, 43(3), 425\u2013440.","journal-title":"Journal of Computer and System Sciences"},{"issue":"2","key":"2448_CR28","doi-asserted-by":"crossref","first-page":"307","DOI":"10.1007\/s10107-008-0235-8","volume":"121","author":"F Rendl","year":"2010","unstructured":"Rendl, F., Rinaldi, G., & Wiegele, A. (2010). Solving max-cut to optimality by intersecting semidefinite and polyhedral relaxations. Mathematical Programming, 121(2), 307\u2013335.","journal-title":"Mathematical Programming"},{"key":"2448_CR29","unstructured":"Rinaldi, G. Rudy, a graph generator. \n                        https:\/\/www-user.tu-chemnitz.de\/~helmberg\/sdp_software.html\n                        \n                    ."},{"key":"2448_CR30","unstructured":"Scholvin, J. K. (1999). Approximating the longest path problem with heuristics: A survey. Master\u2019s thesis, University of Illinois at Chicago."},{"key":"2448_CR31","doi-asserted-by":"crossref","first-page":"545","DOI":"10.1016\/j.cam.2013.11.021","volume":"270","author":"MH Seyed","year":"2014","unstructured":"Seyed, M. H., Sai, H. T., & Omid, M. (2014). A genetic algorithm for optimization of integrated scheduling of cranes, vehicles, and storage platforms at automated container terminals. Journal of Computational and Applied Mathematics, 270, 545\u2013556. (Fourth international conference on finite element methods in engineering and sciences (FEMTEC 2013)).","journal-title":"Journal of Computational and Applied Mathematics"},{"issue":"1","key":"2448_CR32","doi-asserted-by":"crossref","first-page":"16","DOI":"10.1287\/ijoc.1120.0542","volume":"26","author":"R Sotirov","year":"2014","unstructured":"Sotirov, R. (2014). An efficient semidefinite programming relaxation for the graph partition problem. INFORMS Journal on Computing, 26(1), 16\u201330.","journal-title":"INFORMS Journal on Computing"},{"issue":"2","key":"2448_CR33","doi-asserted-by":"crossref","first-page":"379","DOI":"10.1007\/s10107-014-0817-6","volume":"151","author":"ER Dam van","year":"2015","unstructured":"van Dam, E. R., & Sotirov, R. (2015). Semidefinite programming and eigenvalue bounds for the graph partition problem. Mathematical Programming, 151(2), 379\u2013404.","journal-title":"Mathematical Programming"},{"key":"2448_CR34","doi-asserted-by":"crossref","first-page":"216","DOI":"10.1016\/j.laa.2015.09.043","volume":"488","author":"ER Dam van","year":"2016","unstructured":"van Dam, E. R., & Sotirov, R. (2016). New bounds for the max-k-cut and chromatic number of a graph. Linear Algebra and its Applications, 488, 216\u2013234.","journal-title":"Linear Algebra and its Applications"},{"key":"2448_CR35","unstructured":"Wiegele, A. (2015). Biq\u00a0mac library-binary quadratic and max cut library. \n                        http:\/\/biqmac.uni-klu.ac.at\/biqmaclib.html\n                        \n                    ."}],"container-title":["Annals of Operations Research"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10479-017-2448-9\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10479-017-2448-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10479-017-2448-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2018,4,19]],"date-time":"2018-04-19T10:36:16Z","timestamp":1524134176000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10479-017-2448-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,3,3]]},"references-count":35,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2018,6]]}},"alternative-id":["2448"],"URL":"https:\/\/doi.org\/10.1007\/s10479-017-2448-9","relation":{},"ISSN":["0254-5330","1572-9338"],"issn-type":[{"type":"print","value":"0254-5330"},{"type":"electronic","value":"1572-9338"}],"subject":[],"published":{"date-parts":[[2017,3,3]]}}}