{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,14]],"date-time":"2026-03-14T07:02:49Z","timestamp":1773471769747,"version":"3.50.1"},"reference-count":50,"publisher":"Elsevier BV","issue":"2","license":[{"start":{"date-parts":[[2019,6,1]],"date-time":"2019-06-01T00:00:00Z","timestamp":1559347200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"},{"start":{"date-parts":[[2019,6,1]],"date-time":"2019-06-01T00:00:00Z","timestamp":1559347200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/legal\/tdmrep-license"}],"funder":[{"DOI":"10.13039\/501100002790","name":"Canadian Network for Research and Innovation in Machining Technology, Natural Sciences and Engineering Research Council of Canada","doi-asserted-by":"publisher","award":["418250"],"award-info":[{"award-number":["418250"]}],"id":[{"id":"10.13039\/501100002790","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100002790","name":"Canadian Network for Research and Innovation in Machining Technology, Natural Sciences and Engineering Research Council of Canada","doi-asserted-by":"publisher","award":["312125"],"award-info":[{"award-number":["312125"]}],"id":[{"id":"10.13039\/501100002790","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["elsevier.com","sciencedirect.com"],"crossmark-restriction":true},"short-container-title":["EURO Journal on Computational Optimization"],"published-print":{"date-parts":[[2019,6]]},"DOI":"10.1007\/s13675-019-00110-y","type":"journal-article","created":{"date-parts":[[2019,3,16]],"date-time":"2019-03-16T11:02:41Z","timestamp":1552734161000},"page":"123-151","update-policy":"https:\/\/doi.org\/10.1016\/elsevier_cm_policy","source":"Crossref","is-referenced-by-count":8,"title":["Improving the linear relaxation of maximum k-cut with semidefinite-based constraints"],"prefix":"10.1016","volume":"7","author":[{"given":"VilmarJeft\u00e9","family":"Rodrigues de Sousa","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8258-9116","authenticated-orcid":false,"given":"MiguelF.","family":"Anjos","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3148-5090","authenticated-orcid":false,"given":"S\u00e9bastien","family":"Le\u00a0Digabel","sequence":"additional","affiliation":[]}],"member":"78","reference":[{"issue":"Supplement C","key":"10.1007\/s13675-019-00110-y_CR1","doi-asserted-by":"crossref","first-page":"333","DOI":"10.1016\/j.endm.2016.03.044","article-title":"An extended edge-representative formulation for the k-partitioning problem","volume":"52","author":"Ales","year":"2016","journal-title":"Electron Notes Discrete Math"},{"key":"10.1007\/s13675-019-00110-y_CR2","doi-asserted-by":"crossref","unstructured":"Anjos MF, Ghaddar B, Hupp L, Liers F, Wiegele A (2013) Solving k-way graph partitioning problems to optimality: the impact of semidefinite relaxations and the bundle method. In: J\u00fcnger Michael, Reinelt Gerhard (eds) Facets of combinatorial optimization. Springer, Berlin, pp 355\u2013386. 10.1007\/978-3-642-38189-8_15","DOI":"10.1007\/978-3-642-38189-8_15"},{"issue":"3","key":"10.1007\/s13675-019-00110-y_CR3","doi-asserted-by":"crossref","first-page":"451","DOI":"10.1007\/s10107-003-0423-5","article-title":"Stronger linear programming relaxations of max-cut","volume":"97","author":"Avis","year":"2003","journal-title":"Math Program"},{"issue":"3","key":"10.1007\/s13675-019-00110-y_CR4","doi-asserted-by":"crossref","first-page":"493","DOI":"10.1287\/opre.36.3.493","article-title":"An application of combinatorial optimization to statistical physics and circuit layout design","volume":"36","author":"Barahona","year":"1988","journal-title":"Oper Res"},{"issue":"1","key":"10.1007\/s13675-019-00110-y_CR5","doi-asserted-by":"crossref","first-page":"87","DOI":"10.1007\/BF01581239","article-title":"The partition problem","volume":"59","author":"Chopra","year":"1993","journal-title":"Math Program"},{"issue":"1","key":"10.1007\/s13675-019-00110-y_CR6","doi-asserted-by":"crossref","first-page":"27","DOI":"10.1016\/0166-218X(93)E0175-X","article-title":"Facets of the k-partition polytope","volume":"61","author":"Chopra","year":"1995","journal-title":"Discrete Appl Math"},{"issue":"3","key":"10.1007\/s13675-019-00110-y_CR7","doi-asserted-by":"crossref","first-page":"267","DOI":"10.1023\/B:JOCO.0000038911.67280.3f","article-title":"On approximate graph colouring and max-k-cut algorithms based on the \u03b8-function","volume":"8","author":"de Klerk","year":"2004","journal-title":"J Comb Optim"},{"issue":"2","key":"10.1007\/s13675-019-00110-y_CR8","doi-asserted-by":"crossref","first-page":"201","DOI":"10.1007\/s101070100263","article-title":"Benchmarking optimization software with performance profiles","volume":"91","author":"Dolan","year":"2002","journal-title":"Math Program"},{"key":"10.1007\/s13675-019-00110-y_CR9","doi-asserted-by":"crossref","unstructured":"Eisenbl\u00e4tter A (2002) The semidefinite relaxation of the k-partition polytope is strong. In: Cook WJ, Schulz AS (eds) Integer programming and combinatorial optimization. Lecture notes in computer science, vol 237. Springer, Berlin, pp 273\u2013290. doi:10.1007\/3-540-47867-1_20","DOI":"10.1007\/3-540-47867-1_20"},{"key":"10.1007\/s13675-019-00110-y_CR10","doi-asserted-by":"crossref","first-page":"97","DOI":"10.1016\/j.disopt.2017.08.001","article-title":"Projection results for the k-partition problem","volume":"26","author":"Fairbrother","year":"2017","journal-title":"Discrete Optim"},{"issue":"3","key":"10.1007\/s13675-019-00110-y_CR11","doi-asserted-by":"crossref","first-page":"653","DOI":"10.1007\/s10589-017-9967-9","article-title":"A two-level graph partitioning problem arising in mobile wireless communications","volume":"69","author":"Fairbrother","year":"2018","journal-title":"Comput Optim Appl"},{"issue":"1","key":"10.1007\/s13675-019-00110-y_CR12","doi-asserted-by":"crossref","first-page":"67","DOI":"10.1007\/BF02523688","article-title":"Improved approximation algorithms for maxk-cut and max bisection","volume":"18","author":"Frieze","year":"1997","journal-title":"Algorithmica"},{"issue":"5","key":"10.1007\/s13675-019-00110-y_CR13","first-page":"297","article-title":"Gap inequalities for non-convex mixed-integer quadratic programs","volume":"39","author":"Galli","year":"2011","journal-title":"Oper Res Lett"},{"issue":"1","key":"10.1007\/s13675-019-00110-y_CR14","doi-asserted-by":"crossref","first-page":"155","DOI":"10.1007\/s10479-008-0481-4","article-title":"A branch-and-cut algorithm based on semidefinite programming for the minimum k-partition problem","volume":"188","author":"Ghaddar","year":"2011","journal-title":"Ann Oper Res"},{"issue":"6","key":"10.1007\/s13675-019-00110-y_CR15","doi-asserted-by":"crossref","first-page":"1115","DOI":"10.1145\/227683.227684","article-title":"Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming","volume":"42","author":"Goemans","year":"1995","journal-title":"J ACM"},{"key":"10.1007\/s13675-019-00110-y_CR16","doi-asserted-by":"crossref","first-page":"587","DOI":"10.1016\/j.ejor.2011.09.017","article-title":"Interior point methods 25 years later","volume":"218","author":"Gondzio","year":"2012","journal-title":"Eur J Oper Res"},{"issue":"1","key":"10.1007\/s13675-019-00110-y_CR17","doi-asserted-by":"crossref","first-page":"47","DOI":"10.1007\/s12532-015-0090-6","article-title":"Large-scale optimization with the primal-dual column generation method","volume":"8","author":"Gondzio","year":"2016","journal-title":"Math Program Comput"},{"key":"10.1007\/s13675-019-00110-y_CR18","unstructured":"Guennebaud G, Jacob B, et\u00a0al (2010) Eigen. http:\/\/eigen.tuxfamily.org. Accessed Feb 2018"},{"issue":"3","key":"10.1007\/s13675-019-00110-y_CR19","doi-asserted-by":"crossref","first-page":"297","DOI":"10.1016\/j.disc.2005.12.003","article-title":"Minimal triangulations of graphs: a survey","volume":"306","author":"Heggernes","year":"2006","journal-title":"Discrete Math"},{"key":"10.1007\/s13675-019-00110-y_CR20","series-title":"Semidefinite programming for combinatorial optimization","author":"Helmberg","year":"2000"},{"issue":"3","key":"10.1007\/s13675-019-00110-y_CR21","doi-asserted-by":"crossref","first-page":"291","DOI":"10.1007\/BF01580072","article-title":"Solving quadratic (0,1)-problems by semidefinite programs and cutting planes","volume":"82","author":"Helmberg","year":"1998","journal-title":"Math Program"},{"issue":"3","key":"10.1007\/s13675-019-00110-y_CR22","doi-asserted-by":"crossref","first-page":"380","DOI":"10.1137\/1035089","article-title":"Semi-infinite programming: theory, methods, and applications","volume":"35","author":"Hettich","year":"1993","journal-title":"SIAM Rev"},{"issue":"6","key":"10.1007\/s13675-019-00110-y_CR23","doi-asserted-by":"crossref","first-page":"372","DOI":"10.1145\/362248.362272","article-title":"Algorithm 447: efficient algorithms for graph manipulation","volume":"16","author":"Hopcroft","year":"1973","journal-title":"Commun ACM"},{"issue":"2","key":"10.1007\/s13675-019-00110-y_CR24","doi-asserted-by":"crossref","first-page":"246","DOI":"10.1145\/274787.274791","article-title":"Approximate graph coloring by semidefinite programming","volume":"45","author":"Karger","year":"1998","journal-title":"J ACM"},{"key":"10.1007\/s13675-019-00110-y_CR25","unstructured":"Krishnan K, Mitchell JE (2001) Semi-infinite linear programming approaches to semidefinite programming problems. Technical Report\u00a037, Fields Institute Communications Series"},{"issue":"1","key":"10.1007\/s13675-019-00110-y_CR26","doi-asserted-by":"crossref","first-page":"51","DOI":"10.1007\/s10589-005-5958-3","article-title":"A semidefinite programming based polyhedral cut and price approach for the maxcut problem","volume":"33","author":"Krishnan","year":"2006","journal-title":"Comput Optim Appl"},{"issue":"1","key":"10.1007\/s13675-019-00110-y_CR27","first-page":"61","article-title":"Improved semidefinite bounding procedure for solving max-cut problems to optimality","volume":"143","author":"Krislock","year":"2012","journal-title":"Math Program"},{"issue":"2","key":"10.1007\/s13675-019-00110-y_CR28","doi-asserted-by":"crossref","first-page":"233","DOI":"10.1006\/eujc.1996.0020","article-title":"Gap inequalities for the cut polytope","volume":"17","author":"Laurent","year":"1996","journal-title":"Eur J Comb"},{"key":"10.1007\/s13675-019-00110-y_CR29","doi-asserted-by":"crossref","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. In: New optimization algorithms in physics. Wiley-VCH Verlag GmbH & Co. KGaA, pp 47\u201369","DOI":"10.1002\/3527603794.ch4"},{"issue":"1","key":"10.1007\/s13675-019-00110-y_CR30","doi-asserted-by":"crossref","first-page":"91","DOI":"10.1007\/s10107-002-0342-x","article-title":"Graph partitioning using linear and semidefinite programming","volume":"95","author":"Lisser","year":"2003","journal-title":"Math Program"},{"issue":"1","key":"10.1007\/s13675-019-00110-y_CR31","doi-asserted-by":"crossref","first-page":"365","DOI":"10.1007\/s10479-016-2234-0","article-title":"A multiple search operator heuristic for the max-k-cut problem","volume":"248","author":"Ma","year":"2017","journal-title":"Ann Oper Res"},{"issue":"4","key":"10.1007\/s13675-019-00110-y_CR32","doi-asserted-by":"crossref","first-page":"1212","DOI":"10.1137\/S1052623497324242","article-title":"Computational experience with an interior point cutting plane algorithm","volume":"10","author":"Mitchell","year":"2000","journal-title":"SIAM J Optim"},{"issue":"7","key":"10.1007\/s13675-019-00110-y_CR33","doi-asserted-by":"crossref","first-page":"683","DOI":"10.1002\/nav.10084","article-title":"Realignment in the National Football League: did they do it right?","volume":"50","author":"Mitchell","year":"2003","journal-title":"Naval Res Logist"},{"key":"10.1007\/s13675-019-00110-y_CR34","doi-asserted-by":"crossref","unstructured":"Mitchell JE, Pardalos PM, Resende MGC (1999) Interior point methods for combinatorial optimization. In: Du D-Z, Pardalos PM (eds) Handbook of combinatorial optimization, vol 1\u20133. Springer, Boston, pp 189\u2013297","DOI":"10.1007\/978-1-4613-0303-9_4"},{"issue":"11","key":"10.1007\/s13675-019-00110-y_CR35","doi-asserted-by":"crossref","first-page":"1097","DOI":"10.1016\/S0305-0548(97)00031-2","article-title":"Variable neighborhood search","volume":"24","author":"Mladenovi\u0107","year":"1997","journal-title":"Comput Oper Res"},{"issue":"1","key":"10.1007\/s13675-019-00110-y_CR36","doi-asserted-by":"crossref","first-page":"172","DOI":"10.1137\/080724083","article-title":"Benchmarking derivative-free optimization algorithms","volume":"20","author":"Mor\u00e9","year":"2009","journal-title":"SIAM J Optim"},{"key":"10.1007\/s13675-019-00110-y_CR37","unstructured":"Mosek ApS (2015) MOSEK http:\/\/www.mosek.com. Accessed Feb 2018"},{"issue":"8","key":"10.1007\/s13675-019-00110-y_CR38","doi-asserted-by":"crossref","first-page":"2026","DOI":"10.1016\/j.cor.2013.02.028","article-title":"Using the primal-dual interior point algorithm within the branch-price-and-cut method","volume":"40","author":"Munari","year":"2013","journal-title":"Comput Oper Res"},{"issue":"6","key":"10.1007\/s13675-019-00110-y_CR39","doi-asserted-by":"crossref","first-page":"887","DOI":"10.1049\/iet-com.2016.1256","article-title":"Femtocell-enhanced multi-target spectrum allocation strategy in LTE-A HetNets","volume":"11","author":"Niu","year":"2017","journal-title":"IET Commun"},{"key":"10.1007\/s13675-019-00110-y_CR40","doi-asserted-by":"crossref","unstructured":"L. Palagi, V. Piccialli, F. Rendl, G. Rinaldi, A. Wiegele. Computational approaches to max-cut. M.F. Anjos, J.B. Lasserre (ed.), Handbook of semidefinite, conic and polynomial optimization: theory, algorithms, software and applications. International series in operations research and management science; 2011. Springer: New York, 821\u2013847.","DOI":"10.1007\/978-1-4614-0769-0_28"},{"issue":"3","key":"10.1007\/s13675-019-00110-y_CR41","doi-asserted-by":"crossref","first-page":"425","DOI":"10.1016\/0022-0000(91)90023-X","article-title":"Optimization, approximation, and complexity classes","volume":"43","author":"Papadimitriou","year":"1991","journal-title":"J Comput Syst Sci"},{"issue":"4","key":"10.1007\/s13675-019-00110-y_CR42","doi-asserted-by":"crossref","first-page":"321","DOI":"10.1007\/s10288-012-0210-3","article-title":"Semidefinite relaxations for partitioning, assignment and ordering problems","volume":"10","author":"Rendl","year":"2012","journal-title":"4OR"},{"issue":"2","key":"10.1007\/s13675-019-00110-y_CR43","doi-asserted-by":"crossref","first-page":"307","DOI":"10.1007\/s10107-008-0235-8","article-title":"Solving max-cut to optimality by intersecting semidefinite and polyhedral relaxations","volume":"121","author":"Rendl","year":"2010","journal-title":"Math Program"},{"key":"10.1007\/s13675-019-00110-y_CR44","unstructured":"Rinaldi G (2018) Rudy, a graph generator. https:\/\/www-user.tu-chemnitz.de\/~helmberg\/sdp_software.html. Accessed Feb 2018"},{"issue":"1","key":"10.1007\/s13675-019-00110-y_CR45","doi-asserted-by":"crossref","first-page":"5","DOI":"10.1007\/s10479-017-2448-9","article-title":"Computational study of valid inequalities for the maximum k-cut problem","volume":"265","author":"Rodrigues de Sousa","year":"2018","journal-title":"Ann Oper Res"},{"issue":"3","key":"10.1007\/s13675-019-00110-y_CR46","doi-asserted-by":"crossref","first-page":"269","DOI":"10.1016\/0378-8733(83)90028-X","article-title":"Network structure and minimum degree","volume":"5","author":"Seidman","year":"1983","journal-title":"Soc Netw"},{"issue":"1-4","key":"10.1007\/s13675-019-00110-y_CR47","doi-asserted-by":"crossref","first-page":"233","DOI":"10.1023\/A:1013819515732","article-title":"Enhancing RLT relaxations via a new class of semidefinite cuts","volume":"22","author":"Sherali","year":"2002","journal-title":"J Glob Optim"},{"key":"10.1007\/s13675-019-00110-y_CR48","series-title":"Semidefinite programming bounds for extremal graph problems","first-page":"265","author":"Shor","year":"1998"},{"key":"10.1007\/s13675-019-00110-y_CR49","unstructured":"Wang G, Hijazi H (2017) Exploiting sparsity for the min k-partition problem. arXiv e-prints. arXiv:1709.00485"},{"key":"10.1007\/s13675-019-00110-y_CR50","unstructured":"Wiegele A (2015) Biq\u00a0mac library\u2014binary quadratic and max cut library. http:\/\/biqmac.uni-klu.ac.at\/biqmaclib.html. Accessed Feb 2018"}],"container-title":["EURO Journal on Computational Optimization"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s13675-019-00110-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s13675-019-00110-y\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S2192440621001131?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S2192440621001131?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s13675-019-00110-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,31]],"date-time":"2025-10-31T03:47:32Z","timestamp":1761882452000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/S2192440621001131"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,6]]},"references-count":50,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2019,6]]}},"alternative-id":["S2192440621001131"],"URL":"https:\/\/doi.org\/10.1007\/s13675-019-00110-y","relation":{},"ISSN":["2192-4406"],"issn-type":[{"value":"2192-4406","type":"print"}],"subject":[],"published":{"date-parts":[[2019,6]]},"assertion":[{"value":"Elsevier","name":"publisher","label":"This article is maintained by"},{"value":"Improving the linear relaxation of maximum k-cut with semidefinite-based constraints","name":"articletitle","label":"Article Title"},{"value":"EURO Journal on Computational Optimization","name":"journaltitle","label":"Journal Title"},{"value":"https:\/\/doi.org\/10.1007\/s13675-019-00110-y","name":"articlelink","label":"CrossRef DOI link to publisher maintained version"},{"value":"article","name":"content_type","label":"Content Type"},{"value":"Copyright \u00a9 2019 The author(s). Published by Elsevier B.V. on behalf of Association of European Operational Research Societies (EURO). Published by Elsevier Ltd All rights reserved.","name":"copyright","label":"Copyright"}]}}