{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,4]],"date-time":"2026-06-04T22:11:28Z","timestamp":1780611088477,"version":"3.54.1"},"reference-count":28,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[1995,7,1]],"date-time":"1995-07-01T00:00:00Z","timestamp":804556800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J Glob Optim"],"published-print":{"date-parts":[[1995,7]]},"DOI":"10.1007\/bf01100205","type":"journal-article","created":{"date-parts":[[2005,2,5]],"date-time":"2005-02-05T11:03:01Z","timestamp":1107601381000},"page":"51-73","source":"Crossref","is-referenced-by-count":150,"title":["A recipe for semidefinite relaxation for (0,1)-quadratic programming"],"prefix":"10.1007","volume":"7","author":[{"given":"S.","family":"Poljak","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"F.","family":"Rendl","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"H.","family":"Wolkowicz","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","reference":[{"key":"CR1","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/0166-218X(92)00119-7","volume":"48","author":"W. Adams","year":"1994","unstructured":"Adams, W. and Dealing, P.M. (1994), On the equivalence between roof duality and Lagrangian duality for unconstrained 0?1 quadratic programming problems.Discrete Appl. Math. 48:1?20.","journal-title":"Discrete Appl. Math."},{"key":"CR2","unstructured":"Alizadeh, F. (1992), Combinatorial optimization with semidefinite matrices. InProceedings of the Second Annual Integer Programming and Combinatorial Optimization Conference, CarnegieMellon University."},{"key":"CR3","doi-asserted-by":"crossref","first-page":"295","DOI":"10.1007\/BF01581273","volume":"58","author":"E. Balas","year":"1993","unstructured":"Balas, E., Ceria, S., and Cornuejols, G. (1993), A lift-and-project cutting plane algorithm for mixed 0?1 programs.Mathematical Programming 58:295?324.","journal-title":"Mathematical Programming"},{"key":"CR4","volume-title":"Updated semidefinite constraints. Technical report","author":"E. Balas","year":"1994","unstructured":"Balas, E., Ceria, S., Cornuejols, G., and Pataki, G. (1994), Updated semidefinite constraints. Technical report, GSIA Carnegie Mellon University, Pittsburgh, PA, 1994. Personal communication."},{"key":"CR5","volume-title":"Constrained Optimization and Lagrange Multipliers","author":"D.P. Bersekas","year":"1982","unstructured":"Bersekas, D.P. (1982),Constrained Optimization and Lagrange Multipliers. Academic Press, New York, NY."},{"issue":"3","key":"CR6","doi-asserted-by":"crossref","first-page":"557","DOI":"10.1007\/BF01585184","volume":"62","author":"C. Delorme","year":"1993","unstructured":"Delorme, C. and Poljak, S. (1993), Laplacian eigenvalues and the maximum cut problem.Math. Programming 62(3):557?574.","journal-title":"Math. Programming"},{"key":"CR7","unstructured":"Falkner, J., Rendl, F., Wolkowicz, H., and Zhao, Q., Semidefinite relaxations for the graph partitioning problem. Research report, University of Waterloo, Waterloo, Ontario, In progress."},{"key":"CR8","first-page":"61","volume":"31","author":"G. Finke","year":"1987","unstructured":"Finke, G., Burkard, R.E., and Rendl, F. (1987), Quadratic assignment problems.Annals of Discrete Mathematics 31:61?82.","journal-title":"Annals of Discrete Mathematics"},{"key":"CR9","volume-title":"Nonconvex Programming","author":"F. Forg\u00f3","year":"1988","unstructured":"Forg\u00f3, F. (1988),Nonconvex Programming. Akad\u00e9miai Kiad\u00f3, Budapest."},{"key":"CR10","doi-asserted-by":"crossref","unstructured":"Goemans, M.X. and Williamson, D.P. (1993), 878-approximation algorithms for max cut and max 2sat. Technical report, Department of Mathematics, MIT.","DOI":"10.1145\/195058.195216"},{"key":"CR11","doi-asserted-by":"crossref","first-page":"231","DOI":"10.1109\/TIT.1979.1056027","volume":"25","author":"W. Haemmers","year":"1979","unstructured":"Haemmers, W. (1979), On some problems of lovasz concerning the shannon capacity of graphs.IEEE Transactions on Information Theory 25:231?232.","journal-title":"IEEE Transactions on Information Theory"},{"key":"CR12","doi-asserted-by":"crossref","first-page":"121","DOI":"10.1007\/BF02612354","volume":"28","author":"P.L. Hammer","year":"1984","unstructured":"Hammer, P.L., Hansen, P., and Simeone, B. (1984), Roof duality, complementation and persistency in quadratic 0?1 optimization.Mathematical Programming 28:121?155.","journal-title":"Mathematical Programming"},{"key":"CR13","unstructured":"Helmberg, C., Rendl, F., Vanderbei, R.J., and Wolkowicz, H., A primal-dual interior point method for the max-min eigenvalue problem.SIAM Journal on Optimization, To appear. Accepted Aug\/94."},{"key":"CR14","volume-title":"Quadratic Lagrangian relaxation for the quadratic assignment problem. Research report","author":"S. Karisch","year":"1995","unstructured":"Karisch, S., Rendl, F., Wolkowicz, H., and Zhao, Q. (1995), Quadratic Lagrangian relaxation for the quadratic assignment problem. Research report, University of Waterloo, Waterloo, Ontario, In progress."},{"key":"CR15","doi-asserted-by":"crossref","unstructured":"Knuth, D.E. (1994), The sandwich theorem.Electronic J. Combinatorics 1:48pp.","DOI":"10.37236\/1193"},{"key":"CR16","doi-asserted-by":"crossref","first-page":"711","DOI":"10.1080\/02331938808843386","volume":"19","author":"F. K\u00f6rner","year":"1988","unstructured":"K\u00f6rner, F. (1988), A tight bound for the boolean quadratic optimization problem and its use in a branch and bound algorithm.Optimization 19:711?721.","journal-title":"Optimization"},{"key":"CR17","doi-asserted-by":"crossref","first-page":"355","DOI":"10.1080\/02331939208843863","volume":"26","author":"F. K\u00f6rner","year":"1992","unstructured":"K\u00f6rner, F. (1992), Remarks on a difficult test problem for quadratic boolean programming.Optimization 26:355?357.","journal-title":"Optimization"},{"key":"CR18","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1109\/TIT.1979.1055985","volume":"25","author":"L. Lov\u00e1sz","year":"1979","unstructured":"Lov\u00e1sz, L. (1979), On the Shannon capacity of a graph.IEEE Transactions on Information Theory 25:1?7.","journal-title":"IEEE Transactions on Information Theory"},{"issue":"2","key":"CR19","doi-asserted-by":"crossref","first-page":"166","DOI":"10.1137\/0801013","volume":"1","author":"L. Lov\u00e1sz","year":"1991","unstructured":"Lov\u00e1sz, L. and Schrijver, A. (1991), Cones of matrices and set-functions and 0?1 optimization.SIAM Journal on Optimization 1(2):166?190.","journal-title":"SIAM Journal on Optimization"},{"key":"CR20","volume-title":"Linear and Nonlinear Programming, Reading","author":"D.G. Luenberger","year":"1984","unstructured":"Luenberger, D.G. (1984),Linear and Nonlinear Programming, Reading. Addison-Wesley, Massachusetts, second edition.","edition":"second edition"},{"key":"CR21","doi-asserted-by":"crossref","first-page":"553","DOI":"10.1137\/0904038","volume":"4","author":"J.J. More\u00e9","year":"1983","unstructured":"More\u00e9, J.J. and Sorensen, D.C. (1983), Computing a trust region step.SIAM J. Sci. Statist. Comput 4:553?572.","journal-title":"SIAM J. Sci. Statist. Comput"},{"key":"CR22","doi-asserted-by":"crossref","unstructured":"Pardalos, P., Rendl, F., and Wolkowicz, H. (1994), The quadratic assignment problem: A survey and recent developments. InProceedings of the DIMACS Workshop on Quadratic Assignment Problems, volume 16 ofDIMACS Series in Discrete Mathematics and Theoretical Computer Science, pages 1?41. American Mathematical Society.","DOI":"10.1090\/dimacs\/016\/01"},{"key":"CR23","unstructured":"Poljak, S. and Wolkowicz, H., Convex relaxations of 0?1 quadratic programming.Annals of Operations Research. To appear."},{"key":"CR24","unstructured":"Rendl, F. and Wolkowicz, H., A projection technique for partitioning the nodes of a graph.Annals of Operations Research. To appear in the special issue of APMOD93."},{"key":"CR25","doi-asserted-by":"crossref","first-page":"425","DOI":"10.1109\/TIT.1979.1056072","volume":"IT-25","author":"A. Schrijver","year":"1979","unstructured":"Schrijver, A. (1979), A comparison of the Delsarte and Lov\u00e1sz bounds.IEEE Trans. Infor. Theory, IT-25:425?429.","journal-title":"IEEE Trans. Infor. Theory"},{"key":"CR26","unstructured":"Stern, R. and Wolkowicz, H., Indefinite trust region subproblems and nonsymmetric eigenvalue perturbations.SIAM J. Optimization, To appear. Accepted June\/93."},{"key":"CR27","doi-asserted-by":"crossref","first-page":"101","DOI":"10.1016\/0024-3795(81)90143-9","volume":"40","author":"H. Wolkowicz","year":"1981","unstructured":"Wolkowicz, H. (1981), Some applications of optimization in matrix theory.Linear Algebra and its Applications 40:101?118.","journal-title":"Linear Algebra and its Applications"},{"key":"CR28","unstructured":"Wolkowicz, H., Multiple indefinite trust region problems and semidefinite programming. Research report, University of Waterloo, 1994. In progress."}],"container-title":["Journal of Global Optimization"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01100205.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF01100205\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01100205","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,4,5]],"date-time":"2020-04-05T16:07:13Z","timestamp":1586102833000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF01100205"}},"subtitle":["In memory of Svata Poljak"],"short-title":[],"issued":{"date-parts":[[1995,7]]},"references-count":28,"journal-issue":{"issue":"1","published-print":{"date-parts":[[1995,7]]}},"alternative-id":["BF01100205"],"URL":"https:\/\/doi.org\/10.1007\/bf01100205","relation":{},"ISSN":["0925-5001","1573-2916"],"issn-type":[{"value":"0925-5001","type":"print"},{"value":"1573-2916","type":"electronic"}],"subject":[],"published":{"date-parts":[[1995,7]]}}}