{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,3]],"date-time":"2025-09-03T10:17:09Z","timestamp":1756894629754},"reference-count":23,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[1994,6,1]],"date-time":"1994-06-01T00:00:00Z","timestamp":770428800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Computing"],"published-print":{"date-parts":[[1994,6]]},"DOI":"10.1007\/bf02238072","type":"journal-article","created":{"date-parts":[[2005,11,15]],"date-time":"2005-11-15T01:21:41Z","timestamp":1132017701000},"page":"123-137","source":"Crossref","is-referenced-by-count":19,"title":["Node and edge relaxations of the Max-cut problem","Knoten- und Kanten-Relaxationen beim Max-Cut Problem"],"prefix":"10.1007","volume":"52","author":[{"given":"S.","family":"Poljak","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"F.","family":"Rendl","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"BF02238072_CR1","doi-asserted-by":"crossref","first-page":"107","DOI":"10.1016\/0167-6377(83)90016-0","volume":"2","author":"F. Barahona","year":"1983","unstructured":"Barahona, F.: The max-cut problem in graphs not contractible toK 5. Oper. Res. Lett.2, 107\u2013111 (1983)","journal-title":"Oper. Res. Lett."},{"key":"BF02238072_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.: An application of combinatorial optimization to statistical physics and circuit layout design. Oper. Res.36, 493\u2013513 (1988).","journal-title":"Oper. Res."},{"key":"BF02238072_CR3","doi-asserted-by":"crossref","first-page":"127","DOI":"10.1007\/BF01587084","volume":"44","author":"F. Barahona","year":"1989","unstructured":"Barahona, F., J\u00fcnger, M., Reinelt, G.: Experiments in quadratic 0\u20131 programming. Math. Programm.44, 127\u2013137 (1989).","journal-title":"Math. Programm."},{"key":"BF02238072_CR4","series-title":"DIMACS Report 91-18","first-page":"30","volume-title":"Combinatorial optimization in science and technology (extended abstracts)","author":"F. Barahona","year":"1991","unstructured":"Barahona, F., Titan, H.: Max mean cuts and max cuts. In: Combinatorial optimization in science and technology (extended abstracts), DIMACS Report 91-18, Rutgers University, New Brunswick, New Jersey, pp. 30\u201345 1991."},{"key":"BF02238072_CR5","doi-asserted-by":"crossref","first-page":"557","DOI":"10.1007\/BF01585184","volume":"62","author":"C. Delorme","year":"1993","unstructured":"Delorme, C., Poljak, S.: Laplacian eigenvalues and the maximum cut problem. Math. Programm.62, 557\u2013574 (1993).","journal-title":"Math. Programm"},{"key":"BF02238072_CR6","unstructured":"deSimone, C., Rinaldi, G.: A cutting plane algorithm for the max-cut problem. Technical Report Report 346, IASI Rome, 1992."},{"key":"BF02238072_CR7","series-title":"Technical Report LIENS-92-18","volume-title":"Applications of cut polyhedra","author":"M. Deza","year":"1992","unstructured":"Deza, M., Laurent, M.: Applications of cut polyhedra. Technical Report LIENS-92-18, Ecole Normale Sup\u00e9rieure, Paris, 1992."},{"key":"BF02238072_CR8","doi-asserted-by":"crossref","first-page":"221","DOI":"10.1137\/0204019","volume":"4","author":"F. O. Hadlock","year":"1975","unstructured":"Hadlock, F. O.: Finding a maximum cut of a planar graph in polynomial time. SIAM J. Comput.4, 221\u2013225 (1975).","journal-title":"SIAM J. Comput."},{"key":"BF02238072_CR9","doi-asserted-by":"crossref","first-page":"85","DOI":"10.1007\/978-1-4684-2001-2_9","volume-title":"Complexity of computer computation","author":"R. M. Karp","year":"1972","unstructured":"Karp, R. M.: Reducibility among combinatorial problems. In: Complexity of computer computation (Miller, R. E., Thather, J. W., eds.), pp. 85\u2013103. New York: Plenum Press 1972."},{"key":"BF02238072_CR10","unstructured":"Laurent, M., Poljak, S.: The metric polytope. Proc. of IPCO 1992 (Balas, E., Cornuejols, G., Kannan, R., eds.), pp. 274\u2013286, 1992."},{"key":"BF02238072_CR11","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-322-92106-2","volume-title":"Combinatorial algorithms for integrated circuit layout","author":"T. Lengauer","year":"1990","unstructured":"Lengauer, T.: Combinatorial algorithms for integrated circuit layout. Chichester: J. Wiley 1990."},{"key":"BF02238072_CR12","doi-asserted-by":"crossref","first-page":"343","DOI":"10.21136\/CMJ.1990.102386","volume":"40","author":"B. Mohar","year":"1990","unstructured":"Mohar, B., Poljak, S.: Eigenvalues and the max-cut problem. Czech. Math. J.40, 343\u2013352 (1990).","journal-title":"Czech. Math. J."},{"key":"BF02238072_CR13","first-page":"502","volume":"10","author":"G. I. Orlova","year":"1972","unstructured":"Orlova G. I., Dorfman, Y. G.: Finding the maximal cut in a graph. Eng. Cybernetics10, 502\u2013504 (1972).","journal-title":"Eng. Cybernetics"},{"key":"BF02238072_CR14","doi-asserted-by":"crossref","first-page":"131","DOI":"10.1007\/BF02247879","volume":"45","author":"P. M. Pardalos","year":"1990","unstructured":"Pardalos, P. M., Rodgers, G. P.: Computational aspects of a branch and bound algorithm for quadratic zero-one programming. Computing45, 131\u2013144 (1990).","journal-title":"Computing"},{"key":"BF02238072_CR15","first-page":"568","volume-title":"Sets, graphs and numbers","author":"S. Poljak","year":"1992","unstructured":"Poljak, S.: Polyhedral and eigenvalue approximations of the max-cut problem. In: Sets, graphs and numbers, (Mikl\u00f3s, D., Hal\u00e1sz, G., Lov\u00e1sz, L., Sz\u00f6nyi, T., eds.), pp. 568\u2013581. Amsterdam: North-Holland 1992."},{"key":"BF02238072_CR16","unstructured":"Poljak, S., Tuza, Zs.: On the expected relative error of the polyhedral approximation of the max-cut. Technical Report Report 92757-OR, Institut f\u00fcr Diskrete Mathematik, Universit\u00e4t Bonn, 1992."},{"key":"BF02238072_CR17","unstructured":"Rendl, F., Poljak, S.: Nonpolyhedral relaxations of graph bisection problems. Technical Report, University of Technology Graz, 1992."},{"key":"BF02238072_CR18","unstructured":"Rendl, F., Poljak, S.: Solving the max-cut problem using eigenvalues. Technical Report, University of Technology Graz, 1991."},{"key":"BF02238072_CR19","unstructured":"Rendl, F., Vanderbei, R. J., Wolkowicz, H.: Interior-point methods for max-min eigenvalue problems. Technical Report SOR-93-15, Princeton University, 1993."},{"key":"BF02238072_CR20","doi-asserted-by":"crossref","first-page":"196","DOI":"10.1515\/9783112479926-022","volume-title":"Advances in mathematical optimization","author":"H. Schramm","year":"1988","unstructured":"Schramm, H., Zowe, J.: A combination of the bundle approach and the trust region concept. In: Advances in mathematical optimization (Guddat, J., et al. eds.), pp. 196\u2013209. Berlin: Akademie Verlag 1988."},{"key":"BF02238072_CR21","doi-asserted-by":"crossref","first-page":"121","DOI":"10.1137\/0802008","volume":"2","author":"H. Schramm","year":"1992","unstructured":"Schramm, H., Zowe, J.: A version of the bundle idea for minimizing a nonsmooth function: conceptual idea, convergence analysis, numerical results. SIAM J. Optimization2, 121\u2013152 (1992).","journal-title":"SIAM J. Optimization"},{"key":"BF02238072_CR22","unstructured":"Scott, D. S.: Block Lanczos software for symmetric eigenvalue problems. Technical Report ORNL\/CSD-48, Oak Ridge National Laboratory, 1979."},{"key":"BF02238072_CR23","volume-title":"Personal communication","author":"H. Simon","year":"1993","unstructured":"Simon, H.: Personal communication. NASA Ames Research Center, Moffett Field, CA, 1993."}],"container-title":["Computing"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF02238072.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF02238072\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF02238072","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,5,5]],"date-time":"2023-05-05T11:53:35Z","timestamp":1683287615000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF02238072"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1994,6]]},"references-count":23,"journal-issue":{"issue":"2","published-print":{"date-parts":[[1994,6]]}},"alternative-id":["BF02238072"],"URL":"https:\/\/doi.org\/10.1007\/bf02238072","relation":{},"ISSN":["0010-485X","1436-5057"],"issn-type":[{"value":"0010-485X","type":"print"},{"value":"1436-5057","type":"electronic"}],"subject":[],"published":{"date-parts":[[1994,6]]}}}