{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,9]],"date-time":"2024-09-09T05:58:54Z","timestamp":1725861534837},"publisher-location":"Cham","reference-count":28,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319426334"},{"type":"electronic","value":"9783319426341"}],"license":[{"start":{"date-parts":[[2016,1,1]],"date-time":"2016-01-01T00:00:00Z","timestamp":1451606400000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2016]]},"DOI":"10.1007\/978-3-319-42634-1_30","type":"book-chapter","created":{"date-parts":[[2016,7,19]],"date-time":"2016-07-19T15:50:21Z","timestamp":1468943421000},"page":"370-384","source":"Crossref","is-referenced-by-count":0,"title":["From Graph Orientation to the Unweighted Maximum Cut"],"prefix":"10.1007","author":[{"given":"Walid","family":"Ben-Ameur","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Antoine","family":"Glorieux","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jos\u00e9","family":"Neto","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2016,7,20]]},"reference":[{"key":"30_CR1","doi-asserted-by":"crossref","first-page":"79","DOI":"10.1016\/S0166-218X(01)00266-9","volume":"119","author":"M Anjos","year":"2002","unstructured":"Anjos, M., Wolkowicz, H.: Strengthened semidefinite relaxations via a second lifting for the Max-Cut problem. Discrete Appl. Math. 119, 79\u2013106 (2002)","journal-title":"Discrete Appl. Math."},{"key":"30_CR2","unstructured":"Ashcraft, C.C., Liu, J.W.H.: Using domain decomposition to find graph bisectors. Technical report CS-95-08, York University (1995)"},{"key":"30_CR3","doi-asserted-by":"crossref","first-page":"157","DOI":"10.1007\/BF02592023","volume":"36","author":"F Barahona","year":"1986","unstructured":"Barahona, F., Mahjoub, A.R.: On the cut polytope. Math. Program. 36, 157\u2013173 (1986)","journal-title":"Math. Program."},{"key":"30_CR4","doi-asserted-by":"crossref","first-page":"493","DOI":"10.1287\/opre.36.3.493","volume":"36","author":"F Barahona","year":"1998","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, 493\u2013513 (1998)","journal-title":"Oper. Res."},{"key":"30_CR5","first-page":"131","volume-title":"Paradigms of Combinatorial Optimization","author":"W Ben-Ameur","year":"2010","unstructured":"Ben-Ameur, W., Mahjoub, A.R., Neto, J.: The maximum cut problem. In: Paschos, V. (ed.) Paradigms of Combinatorial Optimization, pp. 131\u2013172. Wiley-ISTE, Hoboken (2010)"},{"issue":"3","key":"30_CR6","doi-asserted-by":"crossref","first-page":"276","DOI":"10.1504\/IJMOR.2012.046688","volume":"4","author":"W Ben-Ameur","year":"2012","unstructured":"Ben-Ameur, W., Neto, J.: On a gradient-based randomized heuristic for the maximum cut problem. Int. J. Math. Oper. Res. 4(3), 276\u2013293 (2012)","journal-title":"Int. J. Math. Oper. Res."},{"issue":"1","key":"30_CR7","doi-asserted-by":"crossref","first-page":"8","DOI":"10.1002\/net.20220","volume":"52","author":"W Ben-Ameur","year":"2008","unstructured":"Ben-Ameur, W., Neto, J.: Spectral bounds for the maximum cut problem. Networks 52(1), 8\u201313 (2008)","journal-title":"Networks"},{"issue":"1","key":"30_CR8","doi-asserted-by":"crossref","first-page":"15","DOI":"10.1016\/j.ejor.2010.02.042","volume":"207","author":"W Ben-Ameur","year":"2010","unstructured":"Ben-Ameur, W., Neto, J.: Spectral bounds for unconstrained (-1, 1)-quadratic optimization problems. Eur. J. Oper. Res. 207(1), 15\u201324 (2010)","journal-title":"Eur. J. Oper. Res."},{"key":"30_CR9","doi-asserted-by":"crossref","first-page":"1136","DOI":"10.1109\/5.236191","volume":"81","author":"M Calzarossa","year":"1993","unstructured":"Calzarossa, M., Serazzi, G.: Workload characterization: a survey. Proc. IEEE 81, 1136\u20131150 (1993)","journal-title":"Proc. IEEE"},{"key":"30_CR10","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.: Geometry of Cuts and Metrics. Springer, Berlin (1997)"},{"key":"30_CR11","unstructured":"Dolezal, O., Hofmeister, T., Lefmann, H.: A comparison of approximation algorithms for the MaxCut problem, Report CI-\/99, Universit\u00e4t Dortmund (1999)"},{"key":"30_CR12","doi-asserted-by":"crossref","first-page":"1033","DOI":"10.1080\/1055678021000090033","volume":"7","author":"P Festa","year":"2002","unstructured":"Festa, P., Pardalos, P., Resende, M., Ribeiro, C.: Randomized heuristics for the MAX-CUT problem. Optim. Methods Softw. 7, 1033\u20131058 (2002)","journal-title":"Optim. Methods Softw."},{"key":"30_CR13","doi-asserted-by":"crossref","first-page":"451","DOI":"10.1007\/s10107-005-0661-9","volume":"105","author":"I Fischer","year":"2006","unstructured":"Fischer, I., Gruber, G., Rendl, F., Sotirov, R.: Computational experience with a bundle approach for semidefinite cutting plane relaxations of Max-Cut and equipartition. Math. Program. 105, 451\u2013469 (2006)","journal-title":"Math. Program."},{"key":"30_CR14","doi-asserted-by":"crossref","first-page":"455","DOI":"10.1287\/mnsc.22.4.455","volume":"22","author":"F Glover","year":"1975","unstructured":"Glover, F.: Improved linear integer programming formulations of nonlinear integer problems. Manage. Sci. 22, 455\u2013460 (1975)","journal-title":"Manage. Sci."},{"key":"30_CR15","doi-asserted-by":"crossref","first-page":"1115","DOI":"10.1145\/227683.227684","volume":"42","author":"M Goemans","year":"1995","unstructured":"Goemans, M., Williamson, D.: Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. J. ACM 42, 1115\u20131145 (1995)","journal-title":"J. ACM"},{"key":"30_CR16","doi-asserted-by":"crossref","first-page":"23","DOI":"10.1016\/0167-6377(81)90020-1","volume":"1","author":"M Gr\u00f6tschel","year":"1981","unstructured":"Gr\u00f6tschel, M., Pulleyblank, W.R.: Weakly bipartite graphs and the Max-Cut problem. Oper. Res. Lett. 1, 23\u201327 (1981)","journal-title":"Oper. Res. Lett."},{"key":"30_CR17","first-page":"388","volume":"32","author":"P Hammer","year":"1965","unstructured":"Hammer, P.: Some network flow problems solved with pseudo-boolean programming. Oper. Res. 32, 388\u2013399 (1965)","journal-title":"Oper. Res."},{"key":"30_CR18","doi-asserted-by":"crossref","first-page":"798","DOI":"10.1145\/502090.502098","volume":"48","author":"J Hastad","year":"2001","unstructured":"Hastad, J.: Some optimal inapproximability results. J. ACM 48, 798\u2013859 (2001)","journal-title":"J. ACM"},{"key":"30_CR19","unstructured":"Helmberg, C.: A cutting plane algorithm for large scale semidefinite relaxations. Technical report ZR-01-26, Konrad-Zuse-Zentrum Berlin (2001)"},{"key":"30_CR20","doi-asserted-by":"crossref","first-page":"85","DOI":"10.1007\/978-1-4684-2001-2_9","volume-title":"Complexity of Computer Computation","author":"RM Karp","year":"1972","unstructured":"Karp, R.M.: Reducibility among combinatorial problems. In: Miller, R.E., Thatcher, J.W. (eds.) Complexity of Computer Computation, pp. 85\u2013103. Plenum Press, New York (1972)"},{"issue":"1\u20132","key":"30_CR21","doi-asserted-by":"crossref","first-page":"61","DOI":"10.1007\/s10107-012-0594-z","volume":"143","author":"N Krislock","year":"2014","unstructured":"Krislock, N., Malick, J., Roupin, F.: Improved semidefinite bounding procedure for solving Max-Cut problems to optimality. Math. Program. 143(1\u20132), 61\u201386 (2014)","journal-title":"Math. Program."},{"key":"30_CR22","first-page":"345","volume":"2","author":"M Laurent","year":"2001","unstructured":"Laurent, M.: Tighter linear and semidefinite relaxations for Max-Cut based on the Lov\u00e1sz-Schrijver lift-and-project procedure. SIAM J. Optim. 2, 345\u2013375 (2001)","journal-title":"SIAM J. Optim."},{"issue":"3","key":"30_CR23","doi-asserted-by":"crossref","first-page":"470","DOI":"10.1287\/moor.28.3.470.16391","volume":"28","author":"M Laurent","year":"2003","unstructured":"Laurent, M.: A comparison of the Sherali-Adams, Lov\u00e1sz-Schrijver and Lasserre relaxations for 0\u20131 programming. Math. Oper. Res. 28(3), 470\u2013496 (2003)","journal-title":"Math. Oper. Res."},{"key":"30_CR24","doi-asserted-by":"crossref","DOI":"10.1093\/oso\/9780198532897.001.0001","volume-title":"An Atlas of Graphs","author":"RC Read","year":"1998","unstructured":"Read, R.C., Wilson, R.J.: An Atlas of Graphs. Clarendon Press, Oxford (1998)"},{"key":"30_CR25","doi-asserted-by":"crossref","unstructured":"Rendl, F., Rinaldi, G., Wiegele, A.: Solving Max-Cut to optimality by intersecting semidefinite and polyhedral relaxations, IASI Research report 08\u201311 (2008)","DOI":"10.1007\/s10107-008-0235-8"},{"key":"30_CR26","unstructured":"Rothvo\u00df, T.: The Lasserre hierarchy in approximation algorithms. Lecture Notes for the MAPSP Tutorial Preliminary Version (2013)"},{"issue":"3","key":"30_CR27","doi-asserted-by":"crossref","first-page":"555","DOI":"10.1145\/321958.321975","volume":"23","author":"S Sahni","year":"1976","unstructured":"Sahni, S., Gonzalez, T.: P-complete approximation algorithms. J. Assoc. Comput. Mach. 23(3), 555\u2013565 (1976)","journal-title":"J. Assoc. Comput. Mach."},{"key":"30_CR28","unstructured":"Wiegele, A.: Nonlinear Optimization Techniques Applied to Combinatorial Optimization Problems. Ph.D. thesis, Alpen-Adria-Universitt Klagenfurt (2006)"}],"container-title":["Lecture Notes in Computer Science","Computing and Combinatorics"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-42634-1_30","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,6,18]],"date-time":"2024-06-18T09:01:38Z","timestamp":1718701298000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-42634-1_30"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016]]},"ISBN":["9783319426334","9783319426341"],"references-count":28,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-42634-1_30","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2016]]}}}