{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,5]],"date-time":"2026-10-05T13:22:19Z","timestamp":1791206539532,"version":"4.1.0"},"reference-count":28,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2008,12,3]],"date-time":"2008-12-03T00:00:00Z","timestamp":1228262400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Ann Oper Res"],"published-print":{"date-parts":[[2011,8]]},"DOI":"10.1007\/s10479-008-0481-4","type":"journal-article","created":{"date-parts":[[2008,12,2]],"date-time":"2008-12-02T16:56:10Z","timestamp":1228236970000},"page":"155-174","source":"Crossref","is-referenced-by-count":43,"title":["A branch-and-cut algorithm based on semidefinite programming for the minimum k-partition problem"],"prefix":"10.1007","volume":"188","author":[{"given":"Bissan","family":"Ghaddar","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Miguel F.","family":"Anjos","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Frauke","family":"Liers","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2008,12,3]]},"reference":[{"key":"481_CR1","doi-asserted-by":"crossref","first-page":"157","DOI":"10.1007\/BF02592023","volume":"36","author":"F. Barahona","year":"1986","unstructured":"Barahona, F., & Mahjoub, A. (1986). On the cut polytope. Mathematical Programming, 36, 157\u2013173.","journal-title":"Mathematical Programming"},{"key":"481_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, 493\u2013513.","journal-title":"Operations Research"},{"key":"481_CR3","unstructured":"Biq Mac solver. (2007). http:\/\/biqmac.uni-klu.ac.at\/ ."},{"issue":"1\u20134","key":"481_CR4","doi-asserted-by":"crossref","first-page":"613","DOI":"10.1080\/10556789908805765","volume":"11\/12","author":"B. Borchers","year":"1999","unstructured":"Borchers, B. (1999). CSDP, a C library for semidefinite programming. Optimization Methods and Software, 11\/12(1\u20134), 613\u2013623.","journal-title":"Optimization Methods and Software"},{"key":"481_CR5","doi-asserted-by":"crossref","first-page":"151","DOI":"10.1007\/BF02115753","volume":"33","author":"E. Boros","year":"1991","unstructured":"Boros, E., & Hammer, P. (1991). The max-cut problem and quadratic 0\u20131 optimization: Polyhedral aspects, relaxations and bounds. Annals of Operations Research, 33, 151\u2013180.","journal-title":"Annals of Operations Research"},{"key":"481_CR6","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, 87\u2013115.","journal-title":"Mathematical Programming"},{"key":"481_CR7","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 problem. Discrete Applied Mathematics, 61, 27\u201348.","journal-title":"Discrete Applied Mathematics"},{"issue":"3","key":"481_CR8","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., & Warners, J. (2004). Approximate graph colouring and max-k-cut algorithms based on the theta function. Journal of Combinatorial Optimization, 8(3), 267\u2013294.","journal-title":"Journal of Combinatorial Optimization"},{"key":"481_CR9","series-title":"Algorithms and combinatorics","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-04295-9","volume-title":"Geometry of cuts and metrics","author":"M. Deza","year":"1997","unstructured":"Deza, M., & Laurent, M. (1997). Algorithms and combinatorics. Geometry of cuts and metrics. Berlin: Springer."},{"key":"481_CR10","doi-asserted-by":"crossref","first-page":"205","DOI":"10.1090\/dimacs\/004\/16","volume":"4","author":"M. Deza","year":"1991","unstructured":"Deza, M., Gr\u00f6tschel, M., & Laurent, M. (1991). Complete descriptions of small multicut polytopes. Applied Geometry and Discrete Mathematics\u2014The Victor Klee Festschrift, 4, 205\u2013220.","journal-title":"Applied Geometry and Discrete Mathematics\u2014The Victor Klee Festschrift"},{"issue":"1","key":"481_CR11","doi-asserted-by":"crossref","first-page":"189","DOI":"10.1109\/69.979982","volume":"14","author":"J. Domingo-Ferrer","year":"2002","unstructured":"Domingo-Ferrer, J., & Mateo-Sanz, J. M. (2002). Practical data-oriented microaggregation for statistical disclosure control. IEEE Transactions on Knowledge and Data Engineering, 14(1), 189\u2013201.","journal-title":"IEEE Transactions on Knowledge and Data Engineering"},{"key":"481_CR12","doi-asserted-by":"crossref","unstructured":"Eisenbl\u00e4tter, A. (2002). The semidefinite relaxation of the k-partition polytope is strong. In Proceedings of the 9th international IPCO conference on integer programming and combinatorial optimization (Vol.\u00a02337, pp.\u00a0273\u2013290).","DOI":"10.1007\/3-540-47867-1_20"},{"issue":"5","key":"481_CR13","doi-asserted-by":"crossref","first-page":"343","DOI":"10.1016\/S0167-6377(03)00025-7","volume":"31","author":"M. Elf","year":"2003","unstructured":"Elf, M., J\u00fcnger, M., & Rinaldi, G. (2003). Minimizing breaks by maximizing cuts. Operations Research Letters, 31(5), 343\u2013349.","journal-title":"Operations Research Letters"},{"key":"481_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 max k-cut and max bisection. Algorithmica, 18, 67\u201381.","journal-title":"Algorithmica"},{"key":"481_CR15","unstructured":"Ghaddar, B. (2007). A branch-and-cut algorithm based on semidefinite programming for the minimum k -partition problem. Master\u2019s thesis, University of Waterloo"},{"issue":"4","key":"481_CR16","doi-asserted-by":"crossref","first-page":"656","DOI":"10.1137\/S0895480192243516","volume":"7","author":"M. Goemans","year":"1994","unstructured":"Goemans, M., & Williamson, D. (1994). New \u00be-approximation algorithms for the maximum satisfiability problem. SIAM Journal of Discrete Mathematics, 7(4), 656\u2013666.","journal-title":"SIAM Journal of Discrete Mathematics"},{"issue":"3","key":"481_CR17","doi-asserted-by":"crossref","first-page":"291","DOI":"10.1007\/BF01580072","volume":"82","author":"C. Helmberg","year":"1998","unstructured":"Helmberg, C., & Rendl, F. (1998). Solving quadratic (0, 1)-problems by semidefinite programs and cutting planes. Mathematical Programming, Series\u00a0A, 82(3), 291\u2013315.","journal-title":"Mathematical Programming, Series\u00a0A"},{"key":"481_CR18","series-title":"Lecture notes in computer science","doi-asserted-by":"crossref","first-page":"74","DOI":"10.1007\/978-3-540-72792-7_7","volume-title":"IPCO","author":"V. Kaibel","year":"2007","unstructured":"Kaibel, V., Peinhardt, M., & Pfetsch, M. E. (2007). Orbitopal fixing. In M. Fischetti & D. P. Williamson (Eds.), Lecture notes in computer science : Vol. 4513. IPCO (pp.\u00a074\u201388). Berlin: Springer."},{"key":"481_CR19","first-page":"104","volume":"74","author":"L. W. Lee","year":"2006","unstructured":"Lee, L. W., Katzgraber, H. G., & Young, A. P. (2006). Critical behavior of the three- and ten-state short-range Potts glass: A Monte Carlo study. Physical Review B, 74, 104\u2013116.","journal-title":"Physical Review B"},{"key":"481_CR20","doi-asserted-by":"crossref","first-page":"47","DOI":"10.1002\/3527603794.ch4","volume-title":"New optimization algorithms in physics","author":"F. Liers","year":"2004","unstructured":"Liers, F., J\u00fcnger, M., Reinelt, G., & Rinaldi, G. (2004). Computing exact ground states of hard ising spin glass problems by branch-and-cut. In New optimization algorithms in physics (pp.\u00a047\u201368). New York: Wiley."},{"key":"481_CR21","doi-asserted-by":"crossref","first-page":"91","DOI":"10.1007\/s10107-002-0342-x","volume":"95","author":"A. Lisser","year":"2003","unstructured":"Lisser, A., & Rendl, F. (2003). Telecommunication clustering using linear and semidefinite programming. Mathematical Programming, 95, 91\u2013101.","journal-title":"Mathematical Programming"},{"key":"481_CR22","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1109\/TIT.1979.1055985","volume":"IT-25","author":"L. Lov\u00e1sz","year":"1979","unstructured":"Lov\u00e1sz, L. (1979). On the Shannon capacity of a graph. IEEE Transactions Information Theory, IT-25, 1\u20137.","journal-title":"IEEE Transactions Information Theory"},{"key":"481_CR23","unstructured":"Mitchell, J. (2001). Branch-and-cut for the k -way equipartition problem (Technical report). Department of Mathematical Sciences, Rensselaer Polytechnic Institute."},{"issue":"7","key":"481_CR24","doi-asserted-by":"crossref","first-page":"683","DOI":"10.1002\/nav.10084","volume":"50","author":"J. E. 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"},{"key":"481_CR25","doi-asserted-by":"crossref","first-page":"295","DOI":"10.1007\/978-3-540-72792-7_23","volume":"4513","author":"F. Rendl","year":"2007","unstructured":"Rendl, F., Rinaldi, G., & Wiegele, A. (2007). A branch and bound algorithm for max-cut based on combining semidefinite and polyhedral relaxations. Integer Programming and Combinatorial Optimization, 4513, 295\u2013309.","journal-title":"Integer Programming and Combinatorial Optimization"},{"key":"481_CR26","unstructured":"Rinaldi, G. (1996). Rudy. http:\/\/www-user.tu-chemnitz.de\/~helmberg\/rudy.tar.gz ."},{"key":"481_CR27","unstructured":"Spin-glass server. (1996). http:\/\/www.informatik.uni-koeln.de\/ls_juenger\/research\/sgs\/index.html ."},{"key":"481_CR28","unstructured":"Wiegele, A. (2006). Nonlinear optimization techniques applied to combinatorial optimization problems. Ph.D. thesis, Alpen-Adria-Universit\u00e4t Klagenfurt."}],"container-title":["Annals of Operations Research"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10479-008-0481-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10479-008-0481-4\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10479-008-0481-4","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,29]],"date-time":"2019-05-29T18:07:52Z","timestamp":1559153272000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10479-008-0481-4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,12,3]]},"references-count":28,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2011,8]]}},"alternative-id":["481"],"URL":"https:\/\/doi.org\/10.1007\/s10479-008-0481-4","relation":{},"ISSN":["0254-5330","1572-9338"],"issn-type":[{"value":"0254-5330","type":"print"},{"value":"1572-9338","type":"electronic"}],"subject":[],"published":{"date-parts":[[2008,12,3]]}}}