{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,28]],"date-time":"2026-04-28T04:13:22Z","timestamp":1777349602050,"version":"3.51.4"},"reference-count":37,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2002,5,1]],"date-time":"2002-05-01T00:00:00Z","timestamp":1020211200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2002,5,1]],"date-time":"2002-05-01T00:00:00Z","timestamp":1020211200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Journal of Global Optimization"],"published-print":{"date-parts":[[2002,5]]},"DOI":"10.1023\/a:1014004625997","type":"journal-article","created":{"date-parts":[[2002,12,28]],"date-time":"2002-12-28T19:42:56Z","timestamp":1041104576000},"page":"1-41","source":"Crossref","is-referenced-by-count":28,"title":["Lagrangian bounds in multiextremal polynomial and discrete optimization problems"],"prefix":"10.1007","volume":"23","author":[{"given":"Naum Z.","family":"Shor","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Petro I.","family":"Stetsyuk","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"382225_CR1","doi-asserted-by":"crossref","first-page":"13","DOI":"10.1137\/0805002","volume":"5","author":"F. Alizadeh","year":"1995","unstructured":"Alizadeh, F. (1995), Interior point methods in semidefinite programming with applications to combinatorial optimization. SIAM Journal on Optimization 5, 13\u201351.","journal-title":"SIAM Journal on Optimization"},{"key":"382225_CR2","unstructured":"Anjos, M.F. and Wolkowicz, H. A strengthened SDP relaxation via second lifting for the maxcut problem, University ofWaterloo, Department of Combinatorics and Optimization, Research Report CORR 99-55, 28 pp."},{"key":"382225_CR3","doi-asserted-by":"crossref","first-page":"340","DOI":"10.1287\/moor.10.2.340","volume":"10","author":"F. Barahona","year":"1985","unstructured":"Barahona, F., Gr\u00f6tshel, M. and Mahjoub, A. (1985), Facets of the bipartite subgraph polytope Mathematics of Operations Research10, 340\u2013358.","journal-title":"Mathematics of Operations Research"},{"key":"382225_CR4","doi-asserted-by":"crossref","first-page":"157","DOI":"10.1007\/BF02592023","volume":"36","author":"F. Barahona","year":"1986","unstructured":"Barahona, F. and Mahjoub, A. (1986), On the cut polytope. Mathematics Programming, 36, 157\u2013173.","journal-title":"Mathematics Programming"},{"key":"382225_CR5","unstructured":"Berge, C. (1961), Farbung von Graphen, deren samtiche bzv. deren ungerade Kreise starr sind (Zusammenfassung), Wissenschaftliche Zeitschrift, Martin Luther Universitat Halle-Wittenberg, Mathematisch-Naturwissenschaftliche Reihe, pp. 114\u2013115."},{"key":"382225_CR6","unstructured":"Berge, C. (1962), Sur une conjecture relative au probleme des codes optimaux, Communication, 13eme assemblee generake de l'URSI, Tokyo."},{"key":"382225_CR7","unstructured":"Bertsekas, D.P. (1995), Nonlinear Programming, Athena Scientific, Belmont, Massachusetts, P. 646."},{"key":"382225_CR8","doi-asserted-by":"crossref","first-page":"16","DOI":"10.1007\/BF03024137","volume":"14","author":"S.J. Cox","year":"1992","unstructured":"Cox, S.J. (1992), The shape of the ideal column, Mathematical Intelligencer 14, 16\u201331.","journal-title":"Mathematical Intelligencer"},{"key":"382225_CR9","doi-asserted-by":"crossref","first-page":"35","DOI":"10.1007\/BFb0120698","volume":"3","author":"J. Cullum","year":"1975","unstructured":"Cullum, J. Donath, W.E. and Wolfe, P. (1975), The minimization of certain nondifferentiable sums of eigenvalues of symmetric matrices, Mathematical Programming Study 3, 35\u201355.","journal-title":"Mathematical Programming Study"},{"issue":"3","key":"382225_CR10","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\u2013574.","journal-title":"Math. Programming"},{"key":"382225_CR11","first-page":"14","volume":"21","author":"V.F. Demyanov","year":"1980","unstructured":"Demyanov, V.F. and Rubinov, A.M. (1980), On quasidifferentiable functionals, Soviet Mathematics Doklady 21, 14\u201317","journal-title":"Soviet Mathematics Doklady"},{"key":"382225_CR12","volume-title":"Iterative solving of mathematical programming problem (interior point method: algoritms)","author":"I.I. Dikin","year":"1980","unstructured":"Dikin, I.I. and Zorkaltsev, V.I. (1980), Iterative solving of mathematical programming problem (interior point method: algoritms), Nauka, Moscow, (in Russian)."},{"key":"382225_CR13","first-page":"35","volume":"3","author":"W.E. Donath","year":"1972","unstructured":"Donath, W.E. and Hoffman, A.J. (1972), Algorithm for partitioning graphs and computer logic based on eigenvectors of connection matrices, Math. Prog. Study 3, 35\u201355.","journal-title":"Math. Prog. Study"},{"key":"382225_CR14","doi-asserted-by":"crossref","unstructured":"Donath, W.E. and Hoffman, A.J. (1973), Lower bounds for the partitioning of graphs, IBM J. Res. Dev. 17.","DOI":"10.1147\/rd.175.0420"},{"key":"382225_CR15","doi-asserted-by":"crossref","unstructured":"Frieze, A. and Jerum, M. 1995, Improved approximation algorithms for max k-cut and max bisection, Reprint, Carnegi Mellon University, pp. 1-17.","DOI":"10.1007\/3-540-59408-6_37"},{"key":"382225_CR16","first-page":"143","volume":"79","author":"M.X. Goemans","year":"1997","unstructured":"Goemans, M.X. 1997, Semidefinite programming in combinatorial optimization, Math. Programming 79, 143\u2013162.","journal-title":"Math. Programming"},{"key":"382225_CR17","doi-asserted-by":"crossref","first-page":"652","DOI":"10.1073\/pnas.35.11.652","volume":"35","author":"K. Fan","year":"1949","unstructured":"Fan, K. (1949), On a theorem of Weyl concerning the eigenvalues of linear transformations, Proceedings of the National Academy of the Sciences of U.S.A.35, 652\u2013655.","journal-title":"Proceedings of the National Academy of the Sciences of U.S.A."},{"key":"382225_CR18","doi-asserted-by":"crossref","unstructured":"Goemans, M.X. and Williamson, D.P. (1994), 0.878-Approximation algorithms forMAX-CUT and MAX 2SAT, Proceedings of the 26th Annual ACM Symposium on Theory of Computing, 422\u2013431.","DOI":"10.1145\/195058.195216"},{"key":"382225_CR19","doi-asserted-by":"crossref","first-page":"23","DOI":"10.1016\/0167-6377(81)90020-1","volume":"1","author":"M. Gr\u00f6tshel","year":"1981","unstructured":"Gr\u00f6tshel, M. and Pulleyblank, W. (1981), Weakly bipartite graphs and the max-cut problem. Operations Research letters1, 23\u201327.","journal-title":"Operations Research letters"},{"key":"382225_CR20","volume-title":"Combinatorics","author":"M. Gr\u00f6tschel","year":"1988","unstructured":"Gr\u00f6tschel, M., L\u00f3vasz, L. and Schrijver, A. (1988), Geometric Algotithms and Combinatorial Optimization, Vol. 2 Combinatorics. Springer, Berlin."},{"key":"382225_CR21","doi-asserted-by":"crossref","unstructured":"Hilbert, D., \u00d1ber die Darstellung definiter Formen als Summen von Formen quadraten. Math. Ann. Leipzig, 1888, Bd. 22, pp. 342\u2013350.","DOI":"10.1007\/BF01443605"},{"key":"382225_CR22","first-page":"225","volume":"77","author":"M. Lawrent","year":"1997","unstructured":"Lawrent, M., Poljak, S. and Rendl, F. (1997), Connections between the semidefinite relaxations of the max-cut and stable set problems, Math. Programming 77, 225\u2013246.","journal-title":"Math. Programming"},{"key":"382225_CR23","doi-asserted-by":"crossref","first-page":"149","DOI":"10.1017\/S0962492900002646","volume":"5","author":"A.S. Lewis","year":"1996","unstructured":"Lewis, A.S. and Overton, M.L. (1996), Eigenvalue Optimization, Acta Numerica 5, 149\u2013190.","journal-title":"Acta Numerica"},{"key":"382225_CR24","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1109\/TIT.1979.1055985","volume":"1","author":"L. L\u00f3vasz","year":"1979","unstructured":"L\u00f3vasz, L. (1979), On the Shannon-capacity of graph. IEEE Transactions on information theory. IT-25 1, 1\u20137.","journal-title":"IEEE Transactions on information theory"},{"key":"382225_CR25","first-page":"253","volume":"2","author":"L. L\u00f3vasz","year":"1972","unstructured":"L\u00f3vasz, L. (1972), Normal hypergraphs and the perfect graph conjecture, DiscreteMathematics 2, 253\u2013267.","journal-title":"DiscreteMathematics"},{"issue":"3","key":"382225_CR26","first-page":"134","volume":"3","author":"R. McElice","year":"1978","unstructured":"McElice, R., Rodemich, E. and Romsey, Jr. H. (1978), The Lovash bound and some generalization. Journal of combinatorics, Information and System Science. 3(3), 134\u2013152.","journal-title":"Journal of combinatorics, Information and System Science"},{"key":"382225_CR27","unstructured":"Narasimhan, G. and Manber, R. (1990), A generalization of Lovasz's sandwich theorem, Polyhedral combinatorics: Proced. of a DIMACS Workshop AMS."},{"key":"382225_CR28","volume-title":"Problem Complexity and Methods Efficiency in Optimization","author":"A. Nemirovsky","year":"1983","unstructured":"Nemirovsky, A. and Yudin, D.B. (1983), Problem Complexity and Methods Efficiency in Optimization, J. Wiley, New York."},{"key":"382225_CR29","doi-asserted-by":"crossref","unstructured":"Nesterov, Yu. and Nemirovskii, A. (1994), Interior point polynomial algorithm in convex programming, SIAM, p. 406.","DOI":"10.1137\/1.9781611970791"},{"key":"382225_CR30","doi-asserted-by":"crossref","first-page":"8","DOI":"10.1109\/TIT.1956.1056798","volume":"2","author":"C. Shannon","year":"1956","unstructured":"Shannon, C. (1956), The zero-error capacity of a noisy channel. IRe Transactions Information Theory. IT 2, 8-19.","journal-title":"IRe Transactions Information Theory"},{"key":"382225_CR31","first-page":"4","volume":"25","author":"A. Shrijver","year":"1979","unstructured":"Shrijver, A. (1979), A comparison of the Delsarte and Lovash bounds. IEEE Transactions on Information Theory. IT-25, 4.","journal-title":"IEEE Transactions on Information Theory"},{"key":"382225_CR32","volume-title":"Thesis","author":"N.Z. Shor","year":"1970","unstructured":"Shor, N.Z. (1970), Methods of non-differentiable optimization and its applications. Ph.D. Thesis,Institute of Cybernetics of NASU, Kiev, Ukraine."},{"key":"382225_CR33","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4757-6015-6","volume-title":"Nondifferentiable Optimization and Polynomial Problems","author":"N.Z. Shor","year":"1998","unstructured":"Shor, N.Z. (1998), Nondifferentiable Optimization and Polynomial Problems, Kluwer, Dordrecht."},{"key":"382225_CR34","first-page":"100","volume":"2","author":"N.Z. Shor","year":"1995","unstructured":"Shor, N.Z. and Berezovski, O.A. (1995). New algorithms for solving weight max-cut problem, Kibernetika i sistemny analiz2, 100\u2013106.","journal-title":"Kibernetika i sistemny analiz"},{"key":"382225_CR35","volume-title":"Quadratic extremal problems and nondifferentiable optimization","author":"N.Z. Shor","year":"1989","unstructured":"Shor, N.Z. Stetsenko, S.I. (1989), Quadratic extremal problems and nondifferentiable optimization, Naukova dumka, Kiev, (in Russian)."},{"key":"382225_CR36","doi-asserted-by":"crossref","unstructured":"Shor, N.Z. and Stetsyuk, P.I. (1997), Using of r-algorithm modifications for obtaining of global minimum of polynomial functions, Kibernetika i sistemny analiz 4, Kiev.","DOI":"10.1007\/BF02733104"},{"key":"382225_CR37","doi-asserted-by":"crossref","unstructured":"Yannakakis, M. (1978), Node and edge deletion NP-complete problems. Proc. 10th Ann. ACM Symp. on Theory of Computing. New York, pp. 253\u2013264.","DOI":"10.1145\/800133.804355"}],"container-title":["Journal of Global Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1023\/A:1014004625997.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1023\/A:1014004625997\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1023\/A:1014004625997.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,7,1]],"date-time":"2025-07-01T10:38:36Z","timestamp":1751366316000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1023\/A:1014004625997"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2002,5]]},"references-count":37,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2002,5]]}},"alternative-id":["382225"],"URL":"https:\/\/doi.org\/10.1023\/a:1014004625997","relation":{},"ISSN":["0925-5001","1573-2916"],"issn-type":[{"value":"0925-5001","type":"print"},{"value":"1573-2916","type":"electronic"}],"subject":[],"published":{"date-parts":[[2002,5]]}}}