{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,9]],"date-time":"2024-09-09T06:52:48Z","timestamp":1725864768693},"publisher-location":"Cham","reference-count":26,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319455860"},{"type":"electronic","value":"9783319455877"}],"license":[{"start":{"date-parts":[[2016,1,1]],"date-time":"2016-01-01T00:00:00Z","timestamp":1451606400000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2016]]},"DOI":"10.1007\/978-3-319-45587-7_35","type":"book-chapter","created":{"date-parts":[[2016,9,9]],"date-time":"2016-09-09T04:01:21Z","timestamp":1473393681000},"page":"403-413","source":"Crossref","is-referenced-by-count":0,"title":["Sum-of-Squares Rank Upper Bounds for\u00a0Matching Problems"],"prefix":"10.1007","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":[[2016,9,10]]},"reference":[{"key":"35_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"14","DOI":"10.1007\/978-3-642-20807-2_2","volume-title":"Integer Programming and Combinatoral Optimization","author":"YH Au","year":"2011","unstructured":"Au, Y.H., Tun\u00e7el, L.: Complexity analyses of Bienstock\u2013Zuckerberg and Lasserre relaxations on the matching and stable set polytopes. In: G\u00fcnl\u00fck, O., Woeginger, G.J. (eds.) IPCO 2011. LNCS, vol. 6655, pp. 14\u201326. Springer, Heidelberg (2011)"},{"key":"35_CR2","unstructured":"Au, Y., Tun\u00e7el, L.: A comprehensive analysis of polyhedral lift-and-project methods (2013). CoRR, abs\/1312.5972"},{"key":"35_CR3","unstructured":"Avis, D., Bremner, D., Tiwary, H.R., Watanabe, O.: Polynomial size linear programs for non-bipartite matching problems and other problems in P (2014). CoRR, abs\/1408.0807"},{"key":"35_CR4","doi-asserted-by":"crossref","unstructured":"Barak, B., Kelner, J.A., Steurer, D.: Rounding sum-of-squares relaxations. In: STOC, pp. 31\u201340 (2014)","DOI":"10.1145\/2591796.2591886"},{"key":"35_CR5","doi-asserted-by":"crossref","unstructured":"Braun, G., Brown-Cohen, J., Huq, A., Pokutta, S., Raghavendra, P., Roy, A., Weitz, B., Zink, D.: The matching problem has no small symmetric SDP. In: SODA, pp. 1067\u20131078 (2016)","DOI":"10.1137\/1.9781611974331.ch75"},{"key":"35_CR6","doi-asserted-by":"crossref","unstructured":"Chan, S.O., Lee, J.R., Raghavendra, P., Steurer, D.: Approximate constraint satisfaction requires large LP relaxations. In: FOCS, pp. 350\u2013359. IEEE Computer Society (2013)","DOI":"10.1109\/FOCS.2013.45"},{"key":"35_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.: Paths, trees and flowers. Can. J. Math. 17, 449\u2013467 (1965)","journal-title":"Can. J. Math."},{"key":"35_CR8","doi-asserted-by":"crossref","unstructured":"Fawzi, H., Saunderson, J., Parrilo, P.A.: Sparse sums of squares on finite abelian groups and improved semidefinite lifts. Math. Program., 1\u201343 (2016)","DOI":"10.1007\/s10107-015-0977-z"},{"issue":"4","key":"35_CR9","doi-asserted-by":"crossref","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."},{"issue":"1\u20132","key":"35_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.: Linear lower bound on degrees of Positivstellensatz calculus proofs for the parity. Theoret. Comput. Sci. 259(1\u20132), 613\u2013622 (2001)","journal-title":"Theoret. Comput. Sci."},{"key":"35_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"301","DOI":"10.1007\/978-3-642-20807-2_24","volume-title":"Integer Programming and Combinatoral Optimization","author":"AR Karlin","year":"2011","unstructured":"Karlin, A.R., Mathieu, C., Nguyen, C.T.: Integrality gaps of linear and semi-definite programming relaxations for Knapsack. In: G\u00fcnl\u00fck, O., Woeginger, G.J. (eds.) IPCO 2011. LNCS, vol. 6655, pp. 301\u2013314. Springer, Heidelberg (2011)"},{"issue":"3","key":"35_CR12","doi-asserted-by":"crossref","first-page":"796","DOI":"10.1137\/S1052623400366802","volume":"11","author":"JB Lasserre","year":"2001","unstructured":"Lasserre, J.B.: Global optimization with polynomials and the problem of moments. SIAM J. Optim. 11(3), 796\u2013817 (2001)","journal-title":"SIAM J. Optim."},{"issue":"3","key":"35_CR13","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.: 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."},{"key":"35_CR14","doi-asserted-by":"crossref","unstructured":"Lee, J.R., Raghavendra, P., Steurer, D.: Lower bounds on the size of semidefinite programming relaxations. In: Servedio, R.A., Rubinfeld, R. (eds.) STOC, pp. 567\u2013576. ACM (2015)","DOI":"10.1145\/2746539.2746599"},{"issue":"12","key":"35_CR15","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.: Cones of matrices and set-functions and 0\u20131 optimization. SIAM J. Optim. 1(12), 166\u2013190 (1991)","journal-title":"SIAM J. Optim."},{"key":"35_CR16","doi-asserted-by":"crossref","unstructured":"Mathieu, C., Sinclair, A.: Sherali-Adams relaxations of the matching polytope. In: STOC, pp. 293\u2013302 (2009)","DOI":"10.1145\/1536414.1536456"},{"key":"35_CR17","unstructured":"Nesterov, Y.: Global Quadratic Optimization via Conic Relaxation, pp. 363\u2013384. Kluwer Academic Publishers, Dordrecht (2000)"},{"key":"35_CR18","doi-asserted-by":"crossref","unstructured":"O\u2019Donnell, R., Zhou, Y.: Approximability and proof complexity. In: SODA, pp. 1537\u20131556 (2013)","DOI":"10.1137\/1.9781611973105.111"},{"key":"35_CR19","unstructured":"Parrilo, P.: Structured semidefinite programs and semialgebraic geometry methods in robustness and optimization. Ph.D. thesis, California Institute of Technology (2000)"},{"key":"35_CR20","unstructured":"Rothvo\u00df, T.: The Lasserre Hierarchy in Approximation Algorithms \u2013 Lecture Notes for the MAPSP 2013 Tutorial, June 2013"},{"key":"35_CR21","doi-asserted-by":"crossref","unstructured":"Rothvo\u00df, T.: The matching polytope has exponential extension complexity. In: STOC, pp. 263\u2013272 (2014)","DOI":"10.1145\/2591796.2591834"},{"issue":"3","key":"35_CR22","doi-asserted-by":"crossref","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":"6","key":"35_CR23","doi-asserted-by":"crossref","first-page":"731","DOI":"10.1007\/BF01070233","volume":"23","author":"N Shor","year":"1987","unstructured":"Shor, N.: Class of global minimum bounds of polynomial functions. Cybernetics 23(6), 731\u2013734 (1987)","journal-title":"Cybernetics"},{"issue":"1","key":"35_CR24","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.: On a representation of the matching polytope via semidefinite liftings. Math. Oper. Res. 24(1), 1\u20137 (1999)","journal-title":"Math. Oper. Res."},{"issue":"3","key":"35_CR25","doi-asserted-by":"crossref","first-page":"689","DOI":"10.1007\/s10878-013-9662-4","volume":"30","author":"P Worah","year":"2015","unstructured":"Worah, P.: Rank bounds for a hierarchy of Lov\u00e1sz and Schrijver. J. Comb. Optim. 30(3), 689\u2013709 (2015)","journal-title":"J. Comb. Optim."},{"issue":"3","key":"35_CR26","doi-asserted-by":"crossref","first-page":"441","DOI":"10.1016\/0022-0000(91)90024-Y","volume":"43","author":"M Yannakakis","year":"1991","unstructured":"Yannakakis, M.: Expressing combinatorial optimization problems by linear programs. J. Comput. Syst. Sci. 43(3), 441\u2013466 (1991)","journal-title":"J. Comput. Syst. Sci."}],"container-title":["Lecture Notes in Computer Science","Combinatorial Optimization"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-45587-7_35","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2017,6,24]],"date-time":"2017-06-24T22:18:26Z","timestamp":1498342706000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-45587-7_35"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016]]},"ISBN":["9783319455860","9783319455877"],"references-count":26,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-45587-7_35","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2016]]}}}