{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,17]],"date-time":"2026-02-17T11:54:06Z","timestamp":1771329246356,"version":"3.50.1"},"reference-count":40,"publisher":"Springer Science and Business Media LLC","issue":"1-2","license":[{"start":{"date-parts":[[2024,5,25]],"date-time":"2024-05-25T00:00:00Z","timestamp":1716595200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2024,5,25]],"date-time":"2024-05-25T00:00:00Z","timestamp":1716595200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Math. Program."],"published-print":{"date-parts":[[2025,7]]},"DOI":"10.1007\/s10107-024-02093-0","type":"journal-article","created":{"date-parts":[[2024,5,25]],"date-time":"2024-05-25T06:02:04Z","timestamp":1716616924000},"page":"79-114","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Stable set polytopes with high lift-and-project ranks for the Lov\u00e1sz\u2013Schrijver SDP operator"],"prefix":"10.1007","volume":"212","author":[{"given":"Yu Hin","family":"Au","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Levent","family":"Tun\u00e7el","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2024,5,25]]},"reference":[{"key":"2093_CR1","unstructured":"Au, Y.H., Lindzey, N., Tun\u00e7el, L.: On connections between association schemes and analyses of polyhedral and positive semidefinite lift-and-project relaxations. arXiv:2008.08628, (2023)"},{"issue":"1","key":"2093_CR2","doi-asserted-by":"publisher","first-page":"411","DOI":"10.1137\/130950173","volume":"30","author":"YH Au","year":"2016","unstructured":"Au, Y.H., Tun\u00e7el, L.: A comprehensive analysis of polyhedral lift-and-project methods. SIAM J. Discrete Math. 30(1), 411\u2013451 (2016)","journal-title":"SIAM J. Discrete Math."},{"key":"2093_CR3","doi-asserted-by":"publisher","first-page":"103","DOI":"10.1016\/j.disopt.2017.10.001","volume":"27","author":"YH Au","year":"2018","unstructured":"Au, Y.H., Tun\u00e7el, L.: Elementary polytopes with high lift-and-project ranks for strong positive semidefinite operators. Discrete Optim. 27, 103\u2013129 (2018)","journal-title":"Discrete Optim."},{"key":"2093_CR4","doi-asserted-by":"crossref","unstructured":"Au, Y.H., Tun\u00e7el, L.: On rank-monotone graph operations and minimal obstruction graphs for the Lov\u00e1sz-Schrijver SDP hierarchy. arXiv:2401.01476, (2024)","DOI":"10.1007\/s10107-024-02166-0"},{"key":"2093_CR5","unstructured":"Au, Y.H.: A Comprehensive analysis of lift-and-project methods for combinatorial optimization. PhD thesis, University of Waterloo, (2014)"},{"issue":"1\u20133","key":"2093_CR6","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1016\/S0166-218X(98)00136-X","volume":"89","author":"E Balas","year":"1998","unstructured":"Balas, E.: Disjunctive programming: properties of the convex hull of feasible points. Discrete Appl. Math. 89(1\u20133), 3\u201344 (1998)","journal-title":"Discrete Appl. Math."},{"issue":"3, Ser. A","key":"2093_CR7","doi-asserted-by":"publisher","first-page":"295","DOI":"10.1007\/BF01581273","volume":"58","author":"E Balas","year":"1993","unstructured":"Balas, E.: Ceria, Sebasti\u00e1n, Cornu\u00e9jols, G\u00e9rard: a lift-and-project cutting plane algorithm for mixed $$0$$-$$1$$ programs. Math. Programm. 58(3, Ser. A), 295\u2013324 (1993)","journal-title":"Math. Programm."},{"key":"2093_CR8","doi-asserted-by":"publisher","first-page":"339","DOI":"10.1016\/j.endm.2013.10.053","volume":"44","author":"SM Bianchi","year":"2013","unstructured":"Bianchi, S.M., Escalante, M.S., Nasini, G.L., Tun\u00e7el, L.: Lov\u00e1sz\u2013Schrijver SDP-operator and a superclass of near-perfect graphs. Electron. Notes Discret. Math. 44, 339\u2013344 (2013)","journal-title":"Electron. Notes Discret. Math."},{"key":"2093_CR9","doi-asserted-by":"publisher","first-page":"460","DOI":"10.1016\/j.dam.2013.03.028","volume":"164","author":"SM Bianchi","year":"2014","unstructured":"Bianchi, S.M., Escalante, M.S., Nasini, G.L., Tun\u00e7el, L.: Some advances on Lov\u00e1sz\u2013Schrijver semidefinite programming relaxations of the fractional stable set polytope. Discrete Appl. Math. 164, 460\u2013469 (2014)","journal-title":"Discrete Appl. Math."},{"issue":"1\u20132, Ser. A","key":"2093_CR10","doi-asserted-by":"publisher","first-page":"201","DOI":"10.1007\/s10107-016-1035-1","volume":"162","author":"SM Bianchi","year":"2017","unstructured":"Bianchi, S.M., Escalante, M.S., Nasini, G.L., Tun\u00e7el, L.: Lov\u00e1sz\u2013Schrijver SDP-operator, near-perfect graphs and near-bipartite graphs. Math. Program. 162(1\u20132, Ser. A), 201\u2013223 (2017)","journal-title":"Math. Program."},{"key":"2093_CR11","doi-asserted-by":"publisher","first-page":"70","DOI":"10.1016\/j.dam.2023.01.012","volume":"332","author":"SM Bianchi","year":"2023","unstructured":"Bianchi, S.M., Escalante, M.S., Nasini, G.L., Wagler, A.K.: Lov\u00e1sz-Schrijver PSD-operator and the stable set polytope of claw-free graphs. Discrete Appl. Math. 332, 70\u201386 (2023)","journal-title":"Discrete Appl. Math."},{"issue":"1","key":"2093_CR12","doi-asserted-by":"publisher","first-page":"13","DOI":"10.1016\/j.disopt.2004.03.002","volume":"1","author":"D Bienstock","year":"2004","unstructured":"Bienstock, D., Ozbay, N.: Tree-width and the Sherali\u2013Adams operator. Discrete Optim. 1(1), 13\u201321 (2004)","journal-title":"Discrete Optim."},{"issue":"1","key":"2093_CR13","doi-asserted-by":"publisher","first-page":"63","DOI":"10.1137\/S1052623402420346","volume":"15","author":"D Bienstock","year":"2004","unstructured":"Bienstock, D., Zuckerberg, M.: Subset algebra lift operators for 0\u20131 integer programming. SIAM J. Optim. 15(1), 63\u201395 (2004)","journal-title":"SIAM J. Optim."},{"issue":"115","key":"2093_CR14","doi-asserted-by":"publisher","first-page":"455","DOI":"10.1016\/0024-3795(89)90476-X","volume":"114","author":"V Chv\u00e1tal","year":"1989","unstructured":"Chv\u00e1tal, V., Cook, W., Hartmann, M.: On cutting-plane proofs in combinatorial optimization. Linear Algebra Appl. 114(115), 455\u2013499 (1989)","journal-title":"Linear Algebra Appl."},{"issue":"1","key":"2093_CR15","doi-asserted-by":"publisher","first-page":"19","DOI":"10.1287\/moor.26.1.19.10593","volume":"26","author":"W Cook","year":"2001","unstructured":"Cook, W., Dash, S.: On the matrix-cut rank of polyhedra. Math. Oper. Res. 26(1), 19\u201330 (2001)","journal-title":"Math. Oper. Res."},{"key":"2093_CR16","doi-asserted-by":"publisher","first-page":"305","DOI":"10.1016\/0012-365X(73)90167-2","volume":"4","author":"V Chv\u00e1tal","year":"1973","unstructured":"Chv\u00e1tal, V.: Edmonds polytopes and a hierarchy of combinatorial problems. Discrete Math. 4, 305\u2013337 (1973)","journal-title":"Discrete Math."},{"key":"2093_CR17","unstructured":"Desmos online graphing calculator. https:\/\/www.desmos.com\/calculator\/r63dsy4nax. Accessed 22 Mar 2023"},{"issue":"4","key":"2093_CR18","doi-asserted-by":"publisher","first-page":"875","DOI":"10.1137\/S1052623401383248","volume":"12","author":"E De Klerk","year":"2002","unstructured":"De Klerk, E., Pasechnik, D.V.: Approximation of the stability number of a graph via copositive programming. SIAM J. Optim. 12(4), 875\u2013892 (2002)","journal-title":"SIAM J. Optim."},{"issue":"6","key":"2093_CR19","doi-asserted-by":"publisher","first-page":"639","DOI":"10.1016\/j.orl.2005.10.008","volume":"34","author":"MS Escalante","year":"2006","unstructured":"Escalante, M.S., Montelar, M.S., Nasini, G.L.: Minimal $$N_+$$-rank graphs: progress on Lipt\u00e1k and Tun\u00e7el\u2019s conjecture. Oper. Res. Lett. 34(6), 639\u2013646 (2006)","journal-title":"Oper. Res. Lett."},{"key":"2093_CR20","doi-asserted-by":"publisher","first-page":"95","DOI":"10.1007\/978-1-84800-155-8_7","volume-title":"Recent advances in learning and control, Lect. Notes Control Inf. Sci.","author":"MC Grant","year":"2008","unstructured":"Grant, M.C., Boyd, S.P.: Graph implementations for nonsmooth convex programs. In: Blondel, V.D., Boyd, S.P., Kimura, H. (eds.) Recent advances in learning and control, Lect. Notes Control Inf. Sci., vol. 371, pp. 95\u2013171. Springer, London (2008)"},{"key":"2093_CR21","unstructured":"Grant, M.C., Boyd, S.P.: CVX: Matlab software for disciplined convex programming, version 2.1. http:\/\/cvxr.com\/cvx, (March 2014)"},{"issue":"1","key":"2093_CR22","doi-asserted-by":"publisher","first-page":"145","DOI":"10.1007\/s10107-006-0062-8","volume":"110","author":"N Gvozdenovi\u0107","year":"2007","unstructured":"Gvozdenovi\u0107, N., Laurent, M.: Semidefinite bounds for the stability number of a graph via sums of squares of polynomials. Math. Program. 110(1), 145\u2013173 (2007)","journal-title":"Math. Program."},{"issue":"2, Ser. A","key":"2093_CR23","doi-asserted-by":"publisher","first-page":"381","DOI":"10.1007\/s10107-008-0219-8","volume":"120","author":"M Giandomenico","year":"2009","unstructured":"Giandomenico, M., Letchford, A.N., Rossi, F., Smriglio, S.: An application of the Lov\u00e1sz\u2013Schrijver $$M(K, K)$$ operator to the stable set problem. Math. Program. 120(2, Ser. A), 381\u2013401 (2009)","journal-title":"Math. Program."},{"key":"2093_CR24","doi-asserted-by":"crossref","unstructured":"Goemans, M.X.: Semidefinite programming and combinatorial optimization. In: Proceedings of the international congress of mathematicians, vol. III. pp. 657\u2013666 (1998)","DOI":"10.4171\/dms\/1-3\/63"},{"key":"2093_CR25","doi-asserted-by":"publisher","first-page":"275","DOI":"10.1090\/S0002-9904-1958-10224-4","volume":"64","author":"RE Gomory","year":"1958","unstructured":"Gomory, R.E.: Outline of an algorithm for integer solutions to linear programs. Bull. Amer. Math. Soc. 64, 275\u2013278 (1958)","journal-title":"Bull. Amer. Math. Soc."},{"issue":"4","key":"2093_CR26","doi-asserted-by":"publisher","first-page":"2097","DOI":"10.1137\/090746525","volume":"20","author":"J Gouveia","year":"2010","unstructured":"Gouveia, J., Parrilo, P.A., Thomas, R.R.: Theta bodies for polynomial ideals. SIAM J. Optim. 20(4), 2097\u20132118 (2010)","journal-title":"SIAM J. Optim."},{"issue":"1\u20132","key":"2093_CR27","doi-asserted-by":"publisher","first-page":"165","DOI":"10.1007\/s10107-012-0513-3","volume":"141","author":"M Giandomenico","year":"2013","unstructured":"Giandomenico, M., Rossi, F., Smriglio, S.: Strong lift-and-project cutting planes for the stable set problem. Math. Program. 141(1\u20132), 165\u2013192 (2013)","journal-title":"Math. Program."},{"issue":"4","key":"2093_CR28","doi-asserted-by":"publisher","first-page":"796","DOI":"10.1287\/moor.26.4.796.10012","volume":"26","author":"MX Goemans","year":"2001","unstructured":"Goemans, M.X., Tun\u00e7el, L.: When does the positive semidefiniteness constraint help in lifting procedures? Math. Oper. Res. 26(4), 796\u2013815 (2001)","journal-title":"Math. Oper. Res."},{"key":"2093_CR29","doi-asserted-by":"crossref","unstructured":"Lasserre, J.B.: An explicit exact SDP relaxation for nonlinear 0-1 programs. In: Integer programming and combinatorial optimization (Utrecht, 2001), volume 2081 of Lecture Notes in Comput. Sci., pp. 293\u2013303. Springer, Berlin (2001)","DOI":"10.1007\/3-540-45535-3_23"},{"issue":"3","key":"2093_CR30","doi-asserted-by":"publisher","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."},{"issue":"1","key":"2093_CR31","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1109\/TIT.1979.1055985","volume":"25","author":"L Lov\u00e1sz","year":"1979","unstructured":"Lov\u00e1sz, L.: On the Shannon capacity of a graph. IEEE Trans. Inform. Theory 25(1), 1\u20137 (1979)","journal-title":"IEEE Trans. Inform. Theory"},{"key":"2093_CR32","doi-asserted-by":"crossref","unstructured":"Lee, J.R., Raghavendra, P. Steurer, D.: Lower bounds on the size of semidefinite programming relaxations. In: STOC\u201915\u2014Proceedings of the 2015 ACM symposium on theory of computing, pp. 567\u2013576. ACM, New York (2015)","DOI":"10.1145\/2746539.2746599"},{"issue":"2","key":"2093_CR33","doi-asserted-by":"publisher","first-page":"166","DOI":"10.1137\/0801013","volume":"1","author":"L Lov\u00e1sz","year":"1991","unstructured":"Lov\u00e1sz, L., Schrijver, A.: Cones of matrices and set-functions and $$0$$-$$1$$ optimization. SIAM J. Optim. 1(2), 166\u2013190 (1991)","journal-title":"SIAM J. Optim."},{"issue":"1\u20133, Ser. B","key":"2093_CR34","doi-asserted-by":"publisher","first-page":"319","DOI":"10.1007\/s10107-003-0407-5","volume":"98","author":"L Lipt\u00e1k","year":"2003","unstructured":"Lipt\u00e1k, L.: Tun\u00e7el, Levent: The stable set problem and the lift-and-project ranks of graphs. Math. Program. 98(1\u20133, Ser. B), 319\u2013353 (2003)","journal-title":"Math. Program."},{"issue":"1","key":"2093_CR35","doi-asserted-by":"publisher","first-page":"87","DOI":"10.1137\/05064401X","volume":"18","author":"J Pe\u00f1a","year":"2007","unstructured":"Pe\u00f1a, J., Vera, J., Zuluaga, L.F.: Computing the stability number of a graph via linear and semidefinite programming. SIAM J. Optim. 18(1), 87\u2013105 (2007)","journal-title":"SIAM J. Optim."},{"issue":"3","key":"2093_CR36","doi-asserted-by":"publisher","first-page":"411","DOI":"10.1137\/0403036","volume":"3","author":"HD Sherali","year":"1990","unstructured":"Sherali, H.D., Adams, W.P.: A hierarchy of relaxations between the continuous and convex hull representations for zero-one programming problems. SIAM J. Discrete Math. 3(3), 411\u2013430 (1990)","journal-title":"SIAM J. Discrete Math."},{"issue":"1","key":"2093_CR37","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1287\/moor.24.1.1","volume":"24","author":"T Stephen","year":"1999","unstructured":"Stephen, T., Tun\u00e7el, L.: On a representation of the matching polytope via semidefinite liftings. Math. Oper. Res. 24(1), 1\u20137 (1999)","journal-title":"Math. Oper. Res."},{"key":"2093_CR38","doi-asserted-by":"crossref","unstructured":"Schoenebeck, G., Trevisan, L., Tulsiani, M.: Tight integrality gaps for Lovasz-Schrijver LP relaxations of vertex cover and max cut. In: STOC\u201907\u2014Proceedings of the 39th annual ACM symposium on theory of computing, pp. 302\u2013310. ACM, New York (2007)","DOI":"10.1145\/1250790.1250836"},{"issue":"1\u20134","key":"2093_CR39","doi-asserted-by":"publisher","first-page":"625","DOI":"10.1080\/10556789908805766","volume":"11\/12","author":"JF Sturm","year":"1999","unstructured":"Sturm, J.F.: Using SeDuMi 1.02, a MATLAB toolbox for optimization over symmetric cones. Optim. Methods Softw. 11\/12(1\u20134), 625\u2013653 (1999)","journal-title":"Optim. Methods Softw."},{"key":"2093_CR40","doi-asserted-by":"publisher","first-page":"209","DOI":"10.1016\/j.dam.2019.07.017","volume":"308","author":"AK Wagler","year":"2022","unstructured":"Wagler, A.K.: On the Lov\u00e1sz\u2013Schrijver PSD-operator on graph classes defined by clique cutsets. Discrete Appl. Math. 308, 209\u2013219 (2022)","journal-title":"Discrete Appl. Math."}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-024-02093-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10107-024-02093-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-024-02093-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T16:02:43Z","timestamp":1750176163000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10107-024-02093-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,5,25]]},"references-count":40,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2025,7]]}},"alternative-id":["2093"],"URL":"https:\/\/doi.org\/10.1007\/s10107-024-02093-0","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"value":"0025-5610","type":"print"},{"value":"1436-4646","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,5,25]]},"assertion":[{"value":"1 April 2023","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"30 April 2024","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"25 May 2024","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare that they have no Conflict of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}