{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,20]],"date-time":"2026-02-20T21:43:10Z","timestamp":1771623790531,"version":"3.50.1"},"reference-count":29,"publisher":"Springer Science and Business Media LLC","issue":"1-2","license":[{"start":{"date-parts":[[2017,1,4]],"date-time":"2017-01-04T00:00:00Z","timestamp":1483488000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Math. Program."],"published-print":{"date-parts":[[2017,11]]},"DOI":"10.1007\/s10107-016-1102-7","type":"journal-article","created":{"date-parts":[[2017,1,4]],"date-time":"2017-01-04T02:20:14Z","timestamp":1483496414000},"page":"1-17","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":9,"title":["An unbounded Sum-of-Squares hierarchy integrality gap for a polynomially solvable problem"],"prefix":"10.1007","volume":"166","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,1,4]]},"reference":[{"issue":"5","key":"1102_CR1","doi-asserted-by":"crossref","first-page":"1684","DOI":"10.1137\/130911317","volume":"43","author":"N Bansal","year":"2014","unstructured":"Bansal, N., Pruhs, K.: The geometry of scheduling. SIAM J. Comput. 43(5), 1684\u20131698 (2014)","journal-title":"SIAM J. Comput."},{"key":"1102_CR2","doi-asserted-by":"crossref","unstructured":"Barak, B., Chan, S.\u00a0O., Kothar P.\u00a0K.: Sum of squares lower bounds from pairwise independence. In: Proceedings of the 47th Annual ACM on Symposium on Theory of Computing, STOC 2015, Portland, OR, USA, pp. 97\u2013106 (2015)","DOI":"10.1145\/2746539.2746625"},{"key":"1102_CR3","doi-asserted-by":"crossref","unstructured":"Bhaskara, A., Charikar, M., Vijayaraghavan, A., Guruswami, V., Zhou, Y.: Polynomial integrality gaps for strong SDP relaxations of densest $$k$$ k -subgraph. In: Proceedings of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2012, Kyoto, Japan, pp. 388\u2013405 (2012)","DOI":"10.1137\/1.9781611973099.34"},{"key":"1102_CR4","unstructured":"Carr, R.D., Fleischer, L., Leung, V.\u00a0J., Phillips, C.\u00a0A.: Strengthening integrality gaps for capacitated network design and covering problems. In: Proceedings of the 11th Annual ACM-SIAM Symposium on Discrete Algorithms, January 9\u201311, 2000, San Francisco, CA, USA, pp. 106\u2013115 (2000)"},{"issue":"1","key":"1102_CR5","doi-asserted-by":"crossref","first-page":"88","DOI":"10.1287\/moor.1060.0212","volume":"32","author":"KKH Cheung","year":"2007","unstructured":"Cheung, K.K.H.: Computation of the Lasserre ranks of some polytopes. Math. Oper. Res. 32(1), 88\u201394 (2007)","journal-title":"Math. Oper. Res."},{"key":"1102_CR6","doi-asserted-by":"crossref","unstructured":"Cheung, M., Mestre, J., Shmoys, D.\u00a0B., Verschae, J.: A primal-dual approximation algorithm for min-sum single-machine scheduling problems. In: Proceedings of the 14th International Workshop on Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX 2011, and 15th International Workshop, RANDOM 2011, Princeton, NJ, USA, pp. 135\u2013146 (2011)","DOI":"10.1007\/978-3-642-22935-0_12"},{"key":"1102_CR7","doi-asserted-by":"crossref","unstructured":"Chlamtac, E., Tulsiani, M.: Convex relaxations and integrality gaps. In: Anjos, M.F., Lasserre, J.B. (eds.) Handbook on Semidefinite, Conic and Polynomial Optimization, pp. 139\u2013169. Springer, Boston (2012)","DOI":"10.1007\/978-1-4614-0769-0_6"},{"key":"1102_CR8","doi-asserted-by":"crossref","unstructured":"Fawzi, H., Saunderson, J., Parrilo, P.\u00a0A.: Sparse sum-of-squares certificates on finite abelian groups. In: 54th IEEE Conference on Decision and Control, CDC 2015, Osaka, Japan, 2015, pp. 5909\u20135914 (2015)","DOI":"10.1109\/CDC.2015.7403148"},{"issue":"2","key":"1102_CR9","doi-asserted-by":"crossref","first-page":"139","DOI":"10.1007\/s00037-001-8192-0","volume":"10","author":"D Grigoriev","year":"2001","unstructured":"Grigoriev, D.: Complexity of positivstellensatz proofs for the knapsack. Comput. Complex. 10(2), 139\u2013154 (2001)","journal-title":"Comput. Complex."},{"issue":"1\u20132","key":"1102_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. Theor. Comput. Sci. 259(1\u20132), 613\u2013622 (2001)","journal-title":"Theor. Comput. Sci."},{"key":"1102_CR11","doi-asserted-by":"crossref","unstructured":"Karlin, A.\u00a0R., Mathieu, C., Nguyen, C.\u00a0T.: Integrality gaps of linear and semi-definite programming relaxations for knapsack. In: Proceedings of the 15th International Conference on Integer Programming and Combinatoral Optimization, IPCO 2011, New York, NY, USA, pp. 301\u2013314 (2011)","DOI":"10.1007\/978-3-642-20807-2_24"},{"key":"1102_CR12","doi-asserted-by":"crossref","unstructured":"Karp, R.M.: Reducibility among combinatorial problems. In: Proceedings of a Symposium on the Complexity of Computer Computations, Yorktown Heights, New York, pp. 85\u2013103 (1972)","DOI":"10.1007\/978-1-4684-2001-2_9"},{"key":"1102_CR13","unstructured":"Kurpisz, A., Lepp\u00e4nen, S., Mastrolilli, M.: Tight Sum-of-Squares lower bounds for binary polynomial optimization problems. In: Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming, ICALP 2016, Rome, Italy, pp. 78:1\u201314 (2016)"},{"key":"1102_CR14","doi-asserted-by":"crossref","unstructured":"Kurpisz, A., Lepp\u00e4nen, S., Mastrolilli, M.: On the hardest problem formulations for the 0\/1 Lasserre hierarchy. In: Proceedings of the 42nd International Colloquium on Automata, Languages, and Programming, ICALP 2015, Kyoto, Japan, pp. 872\u2013885 (2015)","DOI":"10.1007\/978-3-662-47672-7_71"},{"key":"1102_CR15","doi-asserted-by":"crossref","unstructured":"Kurpisz, A., Lepp\u00e4nen, S., Mastrolilli, M.: Sum-of-squares hierarchy lower bounds for symmetric formulations. In: Proceedings of the 18th International Conference on Integer Programming and Combinatorial Optimization, IPCO 2016, Li\u00e8ge, Belgium, pp. 362\u2013374 (2016)","DOI":"10.1007\/978-3-319-33461-5_30"},{"issue":"3","key":"1102_CR16","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":"1102_CR17","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\u2013Adams, Lov\u00e1sz-Schrijver, and Lasserre relaxations for 0\u20131 programming. Math. Oper. Res. 28(3), 470\u2013496 (2003)","journal-title":"Math. Oper. Res."},{"issue":"4","key":"1102_CR18","doi-asserted-by":"crossref","first-page":"871","DOI":"10.1287\/moor.28.4.871.20508","volume":"28","author":"M Laurent","year":"2003","unstructured":"Laurent, M.: Lower bound for the number of iterations in semidefinite hierarchies for the cut polytope. Math. Oper. Res. 28(4), 871\u2013883 (2003)","journal-title":"Math. Oper. Res."},{"key":"1102_CR19","doi-asserted-by":"crossref","unstructured":"Meka, R., Potechin, A., Wigderson, A.: Sum-of-squares lower bounds for planted clique. In: Proceedings of the 47th Annual ACM on Symposium on Theory of Computing, STOC 2015, Portland, OR, USA, pp. 87\u201396 (2015)","DOI":"10.1145\/2746539.2746600"},{"key":"1102_CR20","unstructured":"Cheung, M., Shmoys, D. B.: A primal-dual approximation algorithm for min-sum single-machine scheduling problems. arXiv:1612.03339v1 [cs.DS]"},{"key":"1102_CR21","doi-asserted-by":"crossref","first-page":"102","DOI":"10.1287\/mnsc.15.1.102","volume":"15","author":"MJ Moore","year":"1968","unstructured":"Moore, M.J.: An $$n$$ n job, one machine sequencing algorithm for minimizing the number of late jobs. Manag. Sci. 15, 102\u2013109 (1968)","journal-title":"Manag. Sci."},{"key":"1102_CR22","doi-asserted-by":"crossref","unstructured":"O\u2019Donnell, R., Zhou, Y.: Approximability and proof complexity. In: Proceedings of the 24th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2013, New Orleans, Louisiana, USA, pp. 1537\u20131556. SIAM (2013)","DOI":"10.1137\/1.9781611973105.111"},{"key":"1102_CR23","unstructured":"Parrilo, P.: Structured semidefinite programs and semialgebraic geometry methods in robustness and optimization. Ph.D. thesis, California Institute of Technology (2000)"},{"key":"1102_CR24","unstructured":"Rothvo\u00df, T.: The Lasserre hierarchy in approximation algorithms. Lecture Notes for the MAPSP 2013 - Tutorial (June 2013)"},{"key":"1102_CR25","unstructured":"Sakaue, S., Takeda, A., Kim, S., Ito, N.: Exact sdp relaxations with truncated moment matrix for binary polynomial optimization problems. In: Proceedings of the 5th International Conference on Continuous Optimization ICCOPT 2016, Tokyo, Japan (2016)"},{"key":"1102_CR26","doi-asserted-by":"crossref","unstructured":"Schoenebeck, G.: Linear level Lasserre lower bounds for certain k-csps. In: Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2008, Philadelphia, PA, USA, pp. 593\u2013602 (2008)","DOI":"10.1109\/FOCS.2008.74"},{"issue":"6","key":"1102_CR27","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"},{"key":"1102_CR28","doi-asserted-by":"crossref","unstructured":"Tulsiani, M.: CSP gaps and reductions in the Lasserre hierarchy. In: Proceedings of the 41st Annual ACM Symposium on Theory of Computing, STOC 2009, Bethesda, MD, USA, pp. 303\u2013312 (2009)","DOI":"10.1145\/1536414.1536457"},{"key":"1102_CR29","doi-asserted-by":"crossref","first-page":"168","DOI":"10.1007\/BF01580441","volume":"8","author":"LA Wolsey","year":"1975","unstructured":"Wolsey, L.A.: Facets for a linear inequality in 0\u20131 variables. Math. Program. 8, 168\u2013175 (1975)","journal-title":"Math. Program."}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10107-016-1102-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-016-1102-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-016-1102-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,9,17]],"date-time":"2019-09-17T00:08:42Z","timestamp":1568678922000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10107-016-1102-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,1,4]]},"references-count":29,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2017,11]]}},"alternative-id":["1102"],"URL":"https:\/\/doi.org\/10.1007\/s10107-016-1102-7","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"value":"0025-5610","type":"print"},{"value":"1436-4646","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,1,4]]}}}