{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,20]],"date-time":"2025-11-20T18:34:10Z","timestamp":1763663650293,"version":"3.37.3"},"reference-count":28,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2017,9,6]],"date-time":"2017-09-06T00:00:00Z","timestamp":1504656000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100001711","name":"Swiss National Science Foundation","doi-asserted-by":"crossref","award":["200020-144491\/1"],"award-info":[{"award-number":["200020-144491\/1"]}],"id":[{"id":"10.13039\/501100001711","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Comb Optim"],"published-print":{"date-parts":[[2018,10]]},"DOI":"10.1007\/s10878-017-0169-2","type":"journal-article","created":{"date-parts":[[2017,9,6]],"date-time":"2017-09-06T21:32:05Z","timestamp":1504733525000},"page":"831-844","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Sum-of-squares rank upper bounds for matching problems"],"prefix":"10.1007","volume":"36","author":[{"given":"Adam","family":"Kurpisz","sequence":"first","affiliation":[]},{"given":"Samuli","family":"Lepp\u00e4nen","sequence":"additional","affiliation":[]},{"given":"Monaldo","family":"Mastrolilli","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2017,9,6]]},"reference":[{"key":"169_CR1","doi-asserted-by":"crossref","unstructured":"Au Y, Tun\u00e7el L (2011) Complexity analyses of Bienstock\u2013Zuckerberg and Lasserre relaxations on the matching and stable set polytopes. In: IPCO, pp 14\u201326","DOI":"10.1007\/978-3-642-20807-2_2"},{"key":"169_CR2","unstructured":"Au Y, Tun\u00e7el L (2013) A comprehensive analysis of polyhedral lift-and-project methods. CoRR. arXiv:1312.5972"},{"key":"169_CR3","unstructured":"Avis D, Bremner D, Tiwary HR, Watanabe O (2014) Polynomial size linear programs for non-bipartite matching problems and other problems in P. CoRR abs\/1408.0807. arXiv:1408.0807"},{"key":"169_CR4","doi-asserted-by":"publisher","unstructured":"Barak B, Kelner JA, Steurer D (2014) Rounding sum-of-squares relaxations. In: STOC, pp 31\u201340. doi: 10.1145\/2591796.2591886","DOI":"10.1145\/2591796.2591886"},{"key":"169_CR5","doi-asserted-by":"publisher","unstructured":"Braun G, Brown-Cohen J, Huq A, Pokutta S, Raghavendra P, Roy A, Weitz B, Zink D (2016) The matching problem has no small symmetric SDP. In: SODA, pp 1067\u20131078. doi: 10.1137\/1.9781611974331.ch75","DOI":"10.1137\/1.9781611974331.ch75"},{"key":"169_CR6","doi-asserted-by":"publisher","unstructured":"Chan SO, Lee JR, Raghavendra P, Steurer D (2013) Approximate constraint satisfaction requires large LP relaxations. In: FOCS. IEEE Computer Society, pp 350\u2013359. doi: 10.1109\/FOCS.2013.45","DOI":"10.1109\/FOCS.2013.45"},{"key":"169_CR7","doi-asserted-by":"crossref","first-page":"449","DOI":"10.4153\/CJM-1965-045-4","volume":"17","author":"J Edmonds","year":"1965","unstructured":"Edmonds J (1965) Paths, trees and flowers. Can J Math 17:449\u2013467","journal-title":"Can J Math"},{"key":"169_CR8","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-015-0977-z","author":"H Fawzi","year":"2016","unstructured":"Fawzi H, Saunderson J, Parrilo PA (2016) Sparse sums of squares on finite Abelian groups and improved semidefinite lifts. Math Program. doi: 10.1007\/s10107-015-0977-z","journal-title":"Math Program"},{"issue":"4","key":"169_CR9","doi-asserted-by":"publisher","first-page":"796","DOI":"10.1287\/moor.26.4.796.10012","volume":"26","author":"MX Goemans","year":"2001","unstructured":"Goemans MX, Tun\u00e7el L (2001) When does the positive semidefiniteness constraint help in lifting procedures? Math Oper Res 26(4):796\u2013815. doi: 10.1287\/moor.26.4.796.10012","journal-title":"Math Oper Res"},{"issue":"1\u20132","key":"169_CR10","doi-asserted-by":"crossref","first-page":"613","DOI":"10.1016\/S0304-3975(00)00157-2","volume":"259","author":"D Grigoriev","year":"2001","unstructured":"Grigoriev D (2001) Linear lower bound on degrees of Positivstellensatz calculus proofs for the parity. Theor Comput Sci 259(1\u20132):613\u2013622","journal-title":"Theor Comput Sci"},{"key":"169_CR11","volume-title":"Matrix analysis","author":"RA Horn","year":"2013","unstructured":"Horn RA, Johnson CR (2013) Matrix analysis. Cambridge University Press, Cambridge"},{"key":"169_CR12","doi-asserted-by":"crossref","unstructured":"Karlin AR, Mathieu C, Nguyen CT (2011) Integrality gaps of linear and semi-definite programming relaxations for Knapsack. In: IPCO, pp 301\u2013314","DOI":"10.1007\/978-3-642-20807-2_24"},{"key":"169_CR13","doi-asserted-by":"crossref","unstructured":"Kurpisz A, Lepp\u00e4nen S, Mastrolilli M (2015) On the hardest problem formulations for the 0\/1 Lasserre hierarchy. In: Automata, languages, and programming\u201442nd international colloquium, ICALP 2015. Proceedings, part I, pp 872\u2013885","DOI":"10.1007\/978-3-662-47672-7_71"},{"issue":"3","key":"169_CR14","doi-asserted-by":"crossref","first-page":"796","DOI":"10.1137\/S1052623400366802","volume":"11","author":"JB Lasserre","year":"2001","unstructured":"Lasserre JB (2001) Global optimization with polynomials and the problem of moments. SIAM J Optim 11(3):796\u2013817","journal-title":"SIAM J Optim"},{"issue":"3","key":"169_CR15","doi-asserted-by":"crossref","first-page":"470","DOI":"10.1287\/moor.28.3.470.16391","volume":"28","author":"M Laurent","year":"2003","unstructured":"Laurent M (2003) A comparison of the Sherali\u2013Adams, Lov\u00e1sz\u2013Schrijver, and Lasserre relaxations for 0\u20131 programming. Math Oper Res 28(3):470\u2013496","journal-title":"Math Oper Res"},{"key":"169_CR16","doi-asserted-by":"publisher","unstructured":"Lee JR, Raghavendra P, Steurer D (2015) Lower bounds on the size of semidefinite programming relaxations. In: Servedio RA, Rubinfeld R (eds) STOC. ACM, pp 567\u2013576. doi: 10.1145\/2746539.2746599","DOI":"10.1145\/2746539.2746599"},{"issue":"12","key":"169_CR17","doi-asserted-by":"crossref","first-page":"166","DOI":"10.1137\/0801013","volume":"1","author":"L Lov\u00e1sz","year":"1991","unstructured":"Lov\u00e1sz L, Schrijver A (1991) Cones of matrices and set-functions and 0\u20131 optimization. SIAM J Optim 1(12):166\u2013190","journal-title":"SIAM J Optim"},{"key":"169_CR18","doi-asserted-by":"publisher","unstructured":"Mathieu C, Sinclair A (2009) Sherali\u2013Adams relaxations of the matching polytope. In: STOC, pp 293\u2013302. doi: 10.1145\/1536414.1536456","DOI":"10.1145\/1536414.1536456"},{"key":"169_CR19","first-page":"363","volume-title":"Global quadratic optimization via conic relaxation","author":"Y Nesterov","year":"2000","unstructured":"Nesterov Y (2000) Global quadratic optimization via conic relaxation. Kluwer Academic Publishers, Dordrecht, pp 363\u2013384"},{"key":"169_CR20","doi-asserted-by":"crossref","unstructured":"O\u2019Donnell R, Zhou Y (2013) Approximability and proof complexity. In: SODA, pp 1537\u20131556","DOI":"10.1137\/1.9781611973105.111"},{"key":"169_CR21","unstructured":"Parrilo P (2000) Structured semidefinite programs and semialgebraic geometry methods in robustness and optimization. Ph.D. Thesis, California Institute of Technology"},{"key":"169_CR22","unstructured":"Rothvo\u00df T (2013) The Lasserre hierarchy in approximation algorithms. In: Lecture Notes for the MAPSP 2013\u2014Tutorial"},{"key":"169_CR23","doi-asserted-by":"publisher","unstructured":"Rothvo\u00df T (2014) The matching polytope has exponential extension complexity. In: STOC, pp 263\u2013272. doi: 10.1145\/2591796.2591834","DOI":"10.1145\/2591796.2591834"},{"issue":"3","key":"169_CR24","doi-asserted-by":"crossref","first-page":"411","DOI":"10.1137\/0403036","volume":"3","author":"HD Sherali","year":"1990","unstructured":"Sherali HD, Adams WP (1990) A hierarchy of relaxations between the continuous and convex hull representations for zero-one programming problems. SIAM J Discrete Math 3(3):411\u2013430","journal-title":"SIAM J Discrete Math"},{"issue":"6","key":"169_CR25","doi-asserted-by":"crossref","first-page":"731","DOI":"10.1007\/BF01070233","volume":"23","author":"N Shor","year":"1987","unstructured":"Shor N (1987) Class of global minimum bounds of polynomial functions. Cybernetics 23(6):731\u2013734","journal-title":"Cybernetics"},{"issue":"1","key":"169_CR26","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1287\/moor.24.1.1","volume":"24","author":"T Stephen","year":"1999","unstructured":"Stephen T, Tun\u00e7el L (1999) On a representation of the matching polytope via semidefinite liftings. Math Oper Res 24(1):1\u20137","journal-title":"Math Oper Res"},{"issue":"3","key":"169_CR27","doi-asserted-by":"publisher","first-page":"689","DOI":"10.1007\/s10878-013-9662-4","volume":"30","author":"P Worah","year":"2015","unstructured":"Worah P (2015) Rank bounds for a hierarchy of Lov\u00e1sz and Schrijver. J Comb Optim 30(3):689\u2013709. doi: 10.1007\/s10878-013-9662-4","journal-title":"J Comb Optim"},{"issue":"3","key":"169_CR28","doi-asserted-by":"publisher","first-page":"441","DOI":"10.1016\/0022-0000(91)90024-Y","volume":"43","author":"M Yannakakis","year":"1991","unstructured":"Yannakakis M (1991) Expressing combinatorial optimization problems by linear programs. J Comput Syst Sci 43(3):441\u2013466. doi: 10.1016\/0022-0000(91)90024-Y","journal-title":"J Comput Syst Sci"}],"container-title":["Journal of Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10878-017-0169-2\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-017-0169-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-017-0169-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,10,3]],"date-time":"2019-10-03T02:02:39Z","timestamp":1570068159000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10878-017-0169-2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,9,6]]},"references-count":28,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2018,10]]}},"alternative-id":["169"],"URL":"https:\/\/doi.org\/10.1007\/s10878-017-0169-2","relation":{},"ISSN":["1382-6905","1573-2886"],"issn-type":[{"type":"print","value":"1382-6905"},{"type":"electronic","value":"1573-2886"}],"subject":[],"published":{"date-parts":[[2017,9,6]]}}}