{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,12]],"date-time":"2026-05-12T04:16:40Z","timestamp":1778559400934,"version":"3.51.4"},"reference-count":45,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2006,1,1]],"date-time":"2006-01-01T00:00:00Z","timestamp":1136073600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2006,1,1]],"date-time":"2006-01-01T00:00:00Z","timestamp":1136073600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Comput Optim Applic"],"published-print":{"date-parts":[[2006,1]]},"DOI":"10.1007\/s10589-005-5958-3","type":"journal-article","created":{"date-parts":[[2006,2,12]],"date-time":"2006-02-12T06:16:20Z","timestamp":1139724980000},"page":"51-71","source":"Crossref","is-referenced-by-count":36,"title":["A Semidefinite Programming Based Polyhedral Cut and Price Approach for the Maxcut Problem"],"prefix":"10.1007","volume":"33","author":[{"given":"Kartik","family":"Krishnan","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"John E.","family":"Mitchell","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"5958_CR1","doi-asserted-by":"crossref","unstructured":"M.F. Anjos and H. Wolkowicz, \u201cStrengthened semidefinite relaxations via a second lifting for the max-cut problem,\u201d Discrete Applied Mathematics, vol. 119, pp. 79\u2013106, 2002.","DOI":"10.1016\/S0166-218X(01)00266-9"},{"key":"5958_CR2","doi-asserted-by":"crossref","unstructured":"D. Avis and J. Umemoto, \u201cStronger linear programming relaxations of max-cut,\u201d Mathematical Programming, vol. 97, pp. 451\u2013469, 2003.","DOI":"10.1007\/s10107-003-0423-5"},{"key":"5958_CR3","doi-asserted-by":"crossref","unstructured":"F. Barahona, M. Gr\u00f6tschel, M. J\u00fcnger, and G. Reinelt, \u201cAn application of combinatorial optimization to statistical physics and circuit layout design,\u201d Operations Research, vol. 36, pp. 493\u2013513, 1998.","DOI":"10.1287\/opre.36.3.493"},{"key":"5958_CR4","doi-asserted-by":"crossref","unstructured":"F. Barahona and A. R. Mahjoub, \u201cOn the cut polytope,\u201d Mathematical Programming, vol. 36, pp. 157\u2013173, 1986.","DOI":"10.1007\/BF02592023"},{"key":"5958_CR5","doi-asserted-by":"crossref","unstructured":"J. Berry and M. Goldberg, \u201cPath optimization for graph partitioning problems,\u201d Discrete Applied Mathematics, vol. 90, pp. 27\u201350, 1999.","DOI":"10.1016\/S0166-218X(98)00084-5"},{"key":"5958_CR6","doi-asserted-by":"crossref","unstructured":"B. Borchers, \u201cSDPLIB 1.2, a library of semidefinite programming test problems,\u201d Optimization Methods and Software, vol. 11, pp. 683\u2013690, 1999.","DOI":"10.1080\/10556789908805769"},{"key":"5958_CR7","doi-asserted-by":"crossref","unstructured":"K. C. Chang and D. Z. Du, \u201cEfficient algorithms for layout assignment problems,\u201d IEEE Transactions on Computer Aided Design, vol. 6, pp. 67\u201378, 1987.","DOI":"10.1109\/TCAD.1987.1270247"},{"key":"5958_CR8","unstructured":"CPLEX Optimization Inc., \u201cCPLEX Linear Optimizer and Mixed Integer Optimizer,\u201d Suite 279, 930 Tahoe Blvd. Bldg 802, Incline Village, NV 89541."},{"key":"5958_CR9","doi-asserted-by":"crossref","unstructured":"C. De Simone, M. Diehl, M. J\u00fcnger, P. Mutzel, G. Reinelt, and G. Rinaldi, \u201cExact ground states of Ising spin glasses: New experimental results with a branch and cut algorithm,\u201d Journal of Statistical Physics, vol. 80, pp. 487\u2013496, 1995.","DOI":"10.1007\/BF02178370"},{"key":"5958_CR10","doi-asserted-by":"crossref","unstructured":"C. De Simone, M. Diehl, M. J\u00fcnger, P. Mutzel, G. Reinelt, and G. Rinaldi, \u201cExact ground states of two-dimensional \u00b1 J Ising spin glasses,\u201d Journal of Statistical Physics, vol. 84, pp. 1363\u20131371, 1996.","DOI":"10.1007\/BF02174135"},{"key":"5958_CR11","doi-asserted-by":"crossref","unstructured":"M.M. Deza and M. Laurent, Geometry of Cuts and Metrics, Springer Verlag: Berlin Heidelberg, 1997.","DOI":"10.1007\/978-3-642-04295-9"},{"key":"5958_CR12","doi-asserted-by":"crossref","unstructured":"S. Elhedhli and J.L. Goffin, \u201cThe integration of an interior-point cutting plane method within a branch-and-price algorithm,\u201d Mathematical Programming, vol. 100, pp. 267\u2013294, 2004.","DOI":"10.1007\/s10107-003-0469-4"},{"key":"5958_CR13","doi-asserted-by":"crossref","unstructured":"M.X. Goemans and D.P. Williamson, \u201cImproved Approximation Algorithms for Maximum Cut and Satisfiability Problems Using Semidefinite Programming,\u201d J. Assoc. Comput. Mach., vol. 42, pp. 1115\u20131145, 1995.","DOI":"10.1145\/227683.227684"},{"key":"5958_CR14","doi-asserted-by":"crossref","unstructured":"B. Grone, C.R. Johnson, E. Marques de Sa, and H. Wolkowicz, \u201cPositive definite completions of partial Hermitian matrices,\u201d Linear Algebra and its Applications, vol. 58, pp. 109\u2013124, 1984.","DOI":"10.1016\/0024-3795(84)90207-6"},{"key":"5958_CR15","doi-asserted-by":"crossref","unstructured":"M. Gr\u00f6tschel, L. Lovasz, and A. Schrijver, Geometric Algorithms and Combinatorial Optimization, Springer-Verlag: Berlin, Germany, 1988.","DOI":"10.1007\/978-3-642-97881-4"},{"key":"5958_CR16","unstructured":"G. Gruber, \u201cOn semidefinite programming and applications in combinatorial optimization,\u201d PhD thesis, University of Technology, Graz, Austria, April 2000."},{"key":"5958_CR17","doi-asserted-by":"crossref","unstructured":"J. Hr\u00e5stad, \u201cSome optimal inapproximability results,\u201d Journal of the ACM, vol. 48, no. 4, pp. 798\u2013859, 2001.","DOI":"10.1145\/502090.502098"},{"key":"5958_CR18","unstructured":"C. Helmberg, \u201cSemidefinite programming for combinatorial optimization,\u201d Technical Report ZR-00-34, TU Berlin, Konrad-Zuse-Zentrum, Berlin, October 2000. Habilitationsschrift. Available from http:\/\/www.zib.de\/PaperWeb\/abstracts\/ZR-00-34."},{"key":"5958_CR19","doi-asserted-by":"crossref","unstructured":"C. Helmberg, \u201cA cutting plane algorithm for large scale semidefinite relaxations,\u201d In The Sharpest Cut, edited by M. Gr\u00f6tschel, Festschrift in honor of M. Padberg's 60th birthday, MPS-SIAM 2004, pp. 233\u2013256.","DOI":"10.1137\/1.9780898718805.ch15"},{"key":"5958_CR20","doi-asserted-by":"crossref","unstructured":"C. Helmberg and F. Rendl, \u201cSolving quadratic (0,1)-problems by semidefinite programs and cutting planes,\u201d Mathematical Programming, vol. 82, pp. 291\u2013315, 1998.","DOI":"10.1007\/BF01580072"},{"key":"5958_CR21","doi-asserted-by":"crossref","unstructured":"H. Karloff, \u201cHow good is the Goemans-Williamson MAX CUT algorithm?\u201d SIAM Journal on Computing, vol. 29, pp. 336\u2013350, 1999.","DOI":"10.1137\/S0097539797321481"},{"key":"5958_CR22","doi-asserted-by":"crossref","unstructured":"R.M. Karp, \u201cReducibility among combinatorial problems,\u201d In: Complexity of Computer Computations, edited by R.E. Miller and J.W. Thatcher, Plenum Press; New York, 1972, pp. 85\u2013103.","DOI":"10.1007\/978-1-4684-2001-2_9"},{"key":"5958_CR23","doi-asserted-by":"crossref","unstructured":"J.E. Kelley, \u201cThe cutting plane method for solving convex programs,\u201d Journal of SIAM, vol. 8, pp. 703\u2013712, 1960.","DOI":"10.1137\/0108053"},{"key":"5958_CR24","doi-asserted-by":"crossref","unstructured":"B.W. Kernighan and S. Lin, \u201cAn efficient heuristic procedure for partitioning graphs,\u201d Bell System Technical Journal, vol. 49, pp. 291\u2013307, 1970.","DOI":"10.1002\/j.1538-7305.1970.tb01770.x"},{"key":"5958_CR25","unstructured":"K. Krishnan, \u201cLinear programming approaches to semidefinite programming problems,\u201d PhD thesis, Mathematical Sciences, Rensselaer Polytechnic Institute, Troy, NY 12180, July 2002."},{"key":"5958_CR26","doi-asserted-by":"crossref","unstructured":"K. Krishnan and J.E. Mitchell, \u201cSemi-infinite linear programming approaches to semidefinite programming (SDP) problems,\u201d Fields Institute Communications Series, Volume 37, Novel approaches to hard discrete optimization problems, edited by P. Pardalos and H. Wolkowicz, pp. 121\u2013140, 2003.","DOI":"10.1090\/fic\/037\/08"},{"key":"5958_CR27","doi-asserted-by":"crossref","unstructured":"K. Krishnan and J.E. Mitchell, \u201cA unifying framework for several cutting plane methods for semidefinite programming\u201d. Optimization Methods and Software, vol. 21, pp. 57\u201374, 2006.","DOI":"10.1080\/10556780500065283"},{"key":"5958_CR28","unstructured":"K. Krishnan and J.E. Mitchell, \u201cProperties of a cutting plane method for semidefinite programming,\u201d Technical report, Mathematical Sciences, Rensselaer Polytechnic Institute, Troy, NY 12180, May 2003. Available from http:\/\/www4.ncsu.edu\/~kksivara\/."},{"key":"5958_CR29","doi-asserted-by":"crossref","unstructured":"K. Krishnan and T. Terlaky, \u201cInterior point and semidefinite approaches in combinatorial optimization,\u201d GERAD 25th anniversary volume on Graph Theory and Combinatorial Optimization, edited by D. Avis, A. Hertz, and O. Marcotte, Springer, pp. 101\u2013157, 2005.","DOI":"10.1007\/0-387-25592-3_5"},{"key":"5958_CR30","doi-asserted-by":"crossref","unstructured":"J.B. Lasserre, \u201cGlobal optimization with polynomials and the problem of moments,\u201d SIAM Journal on Optimization, vol. 11 pp. 796\u2013817, 2001.","DOI":"10.1137\/S1052623400366802"},{"key":"5958_CR31","doi-asserted-by":"crossref","unstructured":"J.B. Lasserre, \u201cAn explicit equivalent semidefinite program for nonlinear 0-1 programs,\u201d SIAM Journal on Optimization, vol. 12, pp. 756-769, 2002.","DOI":"10.1137\/S1052623400380079"},{"key":"5958_CR32","unstructured":"M. Laurent, \u201cA journey from some classical results to the Goemans Williamson approximation algorithm for maxcut,\u201d Lecture given at CORE, Louvain La Neuve, September 1\u201312 2003. Available from http:\/\/homepages.cwl.nl\/~monique\/"},{"key":"5958_CR33","doi-asserted-by":"crossref","unstructured":"M. Laurent and S. Poljak, \u201cOn a positive semidefinite relaxation of the cut polytope,\u201d Linear Algebra and its Applications, vol. 223, pp. 439\u2013461, 1995.","DOI":"10.1016\/0024-3795(95)00271-R"},{"key":"5958_CR34","unstructured":"C. Lemarechal, \u201cNon-differentiable Optimization\u201d in edited by Optimization, G.L. Nemhauser, A.H.G. Rinnooy Kan, and M.J. Todd, eds., North-Holland, New York, 1989 pp. 529\u2013572."},{"key":"5958_CR35","doi-asserted-by":"crossref","unstructured":"J.E. Mitchell, \u201cComputational experience with an interior point cutting plane algorithm,\u201d SIAM Journal on Optimization, vol. 10, pp. 1212\u20131227, 2000.","DOI":"10.1137\/S1052623497324242"},{"key":"5958_CR36","doi-asserted-by":"crossref","unstructured":"Y.E. Nesterov, \u201cSemidefinite relaxation and nonconvex quadratic optimization,\u201d Optimization Methods and Software, vol. 9, pp. 141\u2013160, 1998.","DOI":"10.1080\/10556789808805690"},{"key":"5958_CR37","unstructured":"C.H. Papadimitriou and K. Steiglitz, Combinatorial Optimization: Algorithms and Complexity, Dover Publications Inc.: Mineola, New York, 1998."},{"key":"5958_CR38","doi-asserted-by":"crossref","unstructured":"G. Pataki, \u201cOn the rank of extreme matrices in semidefinite programs and the multiplicity of optimal eigenvalues,\u201d Mathematics of Operations Research, vol. 23, pp. 339\u2013358, 1998.","DOI":"10.1287\/moor.23.2.339"},{"key":"5958_CR39","unstructured":"G. Pataki and S.H. Schmieta, \u201cThe DIMACS library of mixed semidefinite, quadratic, and linear programs,\u201d Available at http:\/\/dimacs.rutgers.edu\/Challenges\/Seventh\/Instances\/"},{"key":"5958_CR40","unstructured":"R.Y. Pinter, \u201cOptimal layer assignment for interconnect,\u201d Journal of VLSI Computational Systems, vol. 1, pp. 123\u2013137, 1984."},{"key":"5958_CR41","doi-asserted-by":"crossref","unstructured":"S. Poljak and Z. Tuza, \u201cMaximum cuts and large bipartite subgraphs,\u201d In \u201cCombinatorial Optimization\u201d, volume 20 of DIMACS Series in Discrete Mathematics and Theoretical Computer Science, AMS\/DIMACS, pp. 181\u2013244, 1995.","DOI":"10.1090\/dimacs\/020\/04"},{"key":"5958_CR42","doi-asserted-by":"crossref","unstructured":"S. Poljak and Z. Tuza, \u201cThe expected relative error of the polyhedral approximation of the maxcut problem,\u201d Operations Research Letters, vol. 16, pp. 191\u2013198, 1994.","DOI":"10.1016\/0167-6377(94)90068-X"},{"key":"5958_CR43","doi-asserted-by":"crossref","unstructured":"K.C. Toh, M.J. Todd, and R. Tutuncu, \u201cSDPT3\u2013 a Matlab software package for semidefinite programming,\u201d Optimization Methods and Software, vol. 11, pp. 545\u2013581, 1999.","DOI":"10.1080\/10556789908805762"},{"key":"5958_CR44","unstructured":"L. Wolsey, \u201cInteger Programming,\u201d John Wiley & Sons, Inc.: New York, 1998."},{"key":"5958_CR45","doi-asserted-by":"crossref","unstructured":"Y. Zhang, \u201cUser's guide to LIPSOL: Linear programming interior point solvers v0.4,\u201d Optimization Methods and Software, vol. 11, pp. 385\u2013396, 1999.","DOI":"10.1080\/10556789908805756"}],"container-title":["Computational Optimization and Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10589-005-5958-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10589-005-5958-3\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10589-005-5958-3","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10589-005-5958-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,5,14]],"date-time":"2022-05-14T05:27:16Z","timestamp":1652506036000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10589-005-5958-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006,1]]},"references-count":45,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2006,1]]}},"alternative-id":["5958"],"URL":"https:\/\/doi.org\/10.1007\/s10589-005-5958-3","relation":{},"ISSN":["0926-6003","1573-2894"],"issn-type":[{"value":"0926-6003","type":"print"},{"value":"1573-2894","type":"electronic"}],"subject":[],"published":{"date-parts":[[2006,1]]}}}