{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,13]],"date-time":"2026-06-13T10:15:45Z","timestamp":1781345745144,"version":"3.54.1"},"reference-count":54,"publisher":"Springer Science and Business Media LLC","issue":"1-2","license":[{"start":{"date-parts":[[2020,5,14]],"date-time":"2020-05-14T00:00:00Z","timestamp":1589414400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2020,5,14]],"date-time":"2020-05-14T00:00:00Z","timestamp":1589414400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"funder":[{"name":"Fondecyt","award":["1181527"],"award-info":[{"award-number":["1181527"]}]},{"name":"Conicyt","award":["PCI PII 20150140"],"award-info":[{"award-number":["PCI PII 20150140"]}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Math. Program."],"published-print":{"date-parts":[[2020,9]]},"DOI":"10.1007\/s10107-020-01511-3","type":"journal-article","created":{"date-parts":[[2020,5,14]],"date-time":"2020-05-14T14:02:41Z","timestamp":1589464961000},"page":"583-618","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Breaking symmetries to rescue sum of squares in the case of makespan scheduling"],"prefix":"10.1007","volume":"183","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-6353-3128","authenticated-orcid":false,"given":"Victor","family":"Verdugo","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jos\u00e9","family":"Verschae","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Andreas","family":"Wiese","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2020,5,14]]},"reference":[{"key":"1511_CR1","unstructured":"Alon, N., Azar, Y., Woeginger, G.J., Yadid, T.: Approximation schemes for scheduling. In: Proceedings of the 8th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 493\u2013500 (1997)"},{"issue":"1","key":"1511_CR2","doi-asserted-by":"publisher","first-page":"55","DOI":"10.1002\/(SICI)1099-1425(199806)1:1<55::AID-JOS2>3.0.CO;2-J","volume":"1","author":"N Alon","year":"1998","unstructured":"Alon, N., Azar, Y., Woeginger, G.J., Yadid, T.: Approximation schemes for scheduling on parallel machines. J. Sched. 1(1), 55\u201366 (1998)","journal-title":"J. Sched."},{"key":"1511_CR3","doi-asserted-by":"crossref","unstructured":"Askey, R.: Orthogonal polynomials and special functions. In: CBMS-NSF Regional Conference Series in Applied Mathematics, vol 21. SIAM (1975)","DOI":"10.1137\/1.9781611970470"},{"key":"1511_CR4","doi-asserted-by":"publisher","first-page":"103","DOI":"10.1016\/j.disopt.2017.10.001","volume":"27","author":"YHG Au","year":"2018","unstructured":"Au, Y.H.G., 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":"1511_CR5","doi-asserted-by":"crossref","unstructured":"Barak, B., Chan, S.O., Kothari, P.K.: Sum of squares lower bounds from pairwise independence. In: Proceedings of the 47th Annual ACM Symposium on Theory of Computing (STOC), pp. 97\u2013106 (2015)","DOI":"10.1145\/2746539.2746625"},{"key":"1511_CR6","doi-asserted-by":"crossref","unstructured":"Barak, B., Hopkins, S.B., Kelner, J., Kothari, P., Moitra, A., Potechin, A.: A nearly tight sum-of-squares lower bound for the planted clique problem. In: Proceedings of the 57th Annual Symposium on Foundations of Computer Science (FOCS), pp. 428\u2013437 (2016)","DOI":"10.1109\/FOCS.2016.53"},{"key":"1511_CR7","unstructured":"Barak, B., Moitra, A.: Noisy tensor completion via the sum-of-squares hierarchy. In: Proceedings of the 29th Conference on Learning Theory (COLT), pp. 417\u2013445 (2016)"},{"issue":"1\u20132","key":"1511_CR8","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1007\/s00209-016-1644-7","volume":"284","author":"G Blekherman","year":"2016","unstructured":"Blekherman, G., Gouveia, J., Pfeiffer, J.: Sums of squares on the hypercube. Math. Z. 284(1\u20132), 41\u201354 (2016)","journal-title":"Math. Z."},{"key":"1511_CR9","doi-asserted-by":"crossref","unstructured":"Chlamtac, E., Tulsiani, M.: Convex relaxations and integrality gaps. In: Handbook on Semidefinite, Conic and Polynomial Optimization, pp 139\u2013169. Springer, Belin (2012)","DOI":"10.1007\/978-1-4614-0769-0_6"},{"key":"1511_CR10","doi-asserted-by":"publisher","DOI":"10.1007\/978-0-387-35651-8","volume-title":"Ideals, Varieties, and Algorithms: An Introduction to Computational Algebraic Geometry and Commutative Algebra. Undergraduate Texts in Mathematics","author":"DA Cox","year":"2007","unstructured":"Cox, D.A., Little, J.B., O\u2019Shea, D.: Ideals, Varieties, and Algorithms: An Introduction to Computational Algebraic Geometry and Commutative Algebra. Undergraduate Texts in Mathematics. Springer, New York (2007)"},{"key":"1511_CR11","doi-asserted-by":"crossref","unstructured":"Eisenbrand, F., Weismantel, R.: Proximity results and faster algorithms for Integer Programming using the Steinitz Lemma. In: Proceedings of the 29th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 808\u2013816 (2018)","DOI":"10.1137\/1.9781611975031.52"},{"key":"1511_CR12","unstructured":"Garg, S.: Quasi-PTAS for scheduling with precedences using LP hierarchies. In: Proceedings of the 45th International Colloquium on Automata, Languages, and Programming (ICALP), pp. 59:1\u201359:13 (2018)"},{"issue":"1\u20133","key":"1511_CR13","doi-asserted-by":"publisher","first-page":"95","DOI":"10.1016\/j.jpaa.2003.12.011","volume":"192","author":"K Gatermann","year":"2004","unstructured":"Gatermann, K., Parrilo, P.A.: Symmetry groups, semidefinite programs, and sums of squares. Journal of Pure and Applied Algebra 192(1\u20133), 95\u2013128 (2004)","journal-title":"Journal of Pure and Applied Algebra"},{"key":"1511_CR14","doi-asserted-by":"crossref","unstructured":"Goemans, M., Rothvo\u00df, T.: Polynomiality for bin packing with a constant number of item types. In: Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 830\u2013839 (2014)","DOI":"10.1137\/1.9781611973402.61"},{"key":"1511_CR15","doi-asserted-by":"publisher","first-page":"1115","DOI":"10.1145\/227683.227684","volume":"42","author":"M Goemans","year":"1995","unstructured":"Goemans, M., Williamson, D.: Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. JACM 42, 1115\u20131145 (1995)","journal-title":"JACM"},{"issue":"9","key":"1511_CR16","doi-asserted-by":"publisher","first-page":"1563","DOI":"10.1002\/j.1538-7305.1966.tb01709.x","volume":"45","author":"RL Graham","year":"1966","unstructured":"Graham, R.L.: Bounds for certain multiprocessing anomalies. Bell Syst. Tech. J. 45(9), 1563\u20131581 (1966)","journal-title":"Bell Syst. Tech. J."},{"issue":"2","key":"1511_CR17","doi-asserted-by":"publisher","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":"1511_CR18","doi-asserted-by":"publisher","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":"1511_CR19","volume-title":"Approximation Algorithms for NP-Hard Problems","author":"D Hochbaum","year":"1996","unstructured":"Hochbaum, D.: Approximation Algorithms for NP-Hard Problems. PWS Publishing Co., Boston (1996)"},{"key":"1511_CR20","doi-asserted-by":"publisher","first-page":"144","DOI":"10.1145\/7531.7535","volume":"34","author":"D Hochbaum","year":"1987","unstructured":"Hochbaum, D., Shmoys, D.: Using dual approximation algorithms for scheduling problems theoretical and practical results. JACM 34, 144\u2013162 (1987)","journal-title":"JACM"},{"key":"1511_CR21","doi-asserted-by":"crossref","unstructured":"Hopkins, S.B., Kothari, P.K., Potechin, A., Raghavendra, P., Schramm, T., Steurer, D.: The power of sum-of-squares for detecting hidden structures. In: Proceedings of the 58th IEEE Annual Symposium on Foundations of Computer Science (FOCS), pp. 720\u2013731 (2017)","DOI":"10.1109\/FOCS.2017.72"},{"issue":"2","key":"1511_CR22","doi-asserted-by":"publisher","first-page":"457","DOI":"10.1137\/090749451","volume":"24","author":"K Jansen","year":"2010","unstructured":"Jansen, K.: An EPTAS for scheduling jobs on uniform processors: using an milp relaxation with a constant number of integral variables. SIAM J. Discrete Math. 24(2), 457\u2013485 (2010)","journal-title":"SIAM J. Discrete Math."},{"key":"1511_CR23","unstructured":"Jansen, K., Klein, K., Verschae, J.: Closing the gap for makespan scheduling via sparsification techniques. In: Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming (ICALP), pp. 72:1\u201372:13 (2016)"},{"key":"1511_CR24","doi-asserted-by":"crossref","unstructured":"Karlin, A., Mathieu, C., Nguyen, C.: 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), pp. 301\u2013314. (2011)","DOI":"10.1007\/978-3-642-20807-2_24"},{"key":"1511_CR25","unstructured":"Kothari, P., O\u2019Donnell, R., Schramm, T.: SOS lower bounds with hard constraints: think global, act local. arXiv:1809.01207 (2018)"},{"key":"1511_CR26","doi-asserted-by":"crossref","unstructured":"Kothari, P.K., Mori, R., O\u2019Donnell, R., Witmer, D.: Sum of squares lower bounds for refuting any CSP. In: Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing (STOC), pp. 132\u2013145 (2017)","DOI":"10.1145\/3055399.3055485"},{"key":"1511_CR27","doi-asserted-by":"crossref","unstructured":"Kothari, P.K., Steinhardt, J., Steurer, D.: Robust moment estimation and improved clustering via sum of squares. In: Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, pp. 1035\u20131046 (2018)","DOI":"10.1145\/3188745.3188970"},{"issue":"1","key":"1511_CR28","doi-asserted-by":"publisher","first-page":"135","DOI":"10.1287\/moor.2016.0797","volume":"42","author":"A Kurpisz","year":"2016","unstructured":"Kurpisz, A., Lepp\u00e4nen, S., Mastrolilli, M.: On the hardest problem formulations for the 0\/1 lasserre hierarchy. Math. Oper. Res. 42(1), 135\u2013143 (2016)","journal-title":"Math. Oper. Res."},{"key":"1511_CR29","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), pp. 362\u2013374 (2016)","DOI":"10.1007\/978-3-319-33461-5_30"},{"issue":"1\u20132","key":"1511_CR30","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s10107-016-1102-7","volume":"166","author":"A Kurpisz","year":"2017","unstructured":"Kurpisz, A., Lepp\u00e4nen, S., Mastrolilli, M.: An unbounded sum-of-squares hierarchy integrality gap for a polynomially solvable problem. Math. Program. 166(1\u20132), 1\u201317 (2017)","journal-title":"Math. Program."},{"issue":"1\u20132","key":"1511_CR31","doi-asserted-by":"publisher","first-page":"231","DOI":"10.1007\/s10107-017-1152-5","volume":"172","author":"A Kurpisz","year":"2018","unstructured":"Kurpisz, A., Mastrolilli, M., Mathieu, C., M\u00f6mke, T., Verdugo, V., Wiese, A.: Semidefinite and linear programming integrality gaps for scheduling identical machines. Math. Program. 172(1\u20132), 231\u2013248 (2018)","journal-title":"Math. Program."},{"key":"1511_CR32","doi-asserted-by":"publisher","first-page":"796","DOI":"10.1137\/S1052623400366802","volume":"11","author":"J Lasserre","year":"2001","unstructured":"Lasserre, J.: Global optimization with polynomials and the problem of moments. SIAM J. Optim. 11, 796\u2013817 (2001)","journal-title":"SIAM J. Optim."},{"key":"1511_CR33","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, 470\u2013496 (2003)","journal-title":"Math. Oper. Res."},{"issue":"4","key":"1511_CR34","doi-asserted-by":"publisher","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."},{"issue":"1","key":"1511_CR35","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s10107-004-0561-4","volume":"109","author":"M Laurent","year":"2007","unstructured":"Laurent, M.: Semidefinite representations for finite varieties. Math. Program. 109(1), 1\u201326 (2007)","journal-title":"Math. Program."},{"key":"1511_CR36","doi-asserted-by":"crossref","unstructured":"Laurent, M.: Sums of squares, moment matrices and optimization over polynomials. In: Emerging Applications of Algebraic Geometry, pp. 157\u2013270. Springer, New York (2009)","DOI":"10.1007\/978-0-387-09686-5_7"},{"key":"1511_CR37","doi-asserted-by":"crossref","unstructured":"Levey, E., Rothvoss, T.: A (1+epsilon)-approximation for makespan scheduling with precedence constraints using LP hierarchies. In: Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing (STOC), pp. 168\u2013177 (2016)","DOI":"10.1145\/2897518.2897532"},{"key":"1511_CR38","doi-asserted-by":"crossref","unstructured":"Ma, T., Shi, J., Steurer, D.: Polynomial-time tensor decompositions with sum-of-squares. In: Foundations of Computer Science (FOCS), pp. 438\u2013446 (2016)","DOI":"10.1109\/FOCS.2016.54"},{"key":"1511_CR39","doi-asserted-by":"crossref","unstructured":"Margot, F.: Symmetry in integer linear programming. In: 50 Years of Integer Programming 1958\u20132008. Springer, Berlin (2010)","DOI":"10.1007\/978-3-540-68279-0_17"},{"key":"1511_CR40","doi-asserted-by":"crossref","unstructured":"Mastrolilli, M.: High degree sum of squares proofs, Bienstock\u2013Zuckerberg hierarchy and cg cuts. In: International Conference on Integer Programming and Combinatorial Optimization, pp. 405\u2013416. Springer, New York (2017)","DOI":"10.1007\/978-3-319-59250-3_33"},{"issue":"2","key":"1511_CR41","doi-asserted-by":"publisher","first-page":"293","DOI":"10.1007\/s10107-003-0387-5","volume":"96","author":"P Parrilo","year":"2003","unstructured":"Parrilo, P.: Semidefinite programming relaxations for semialgebraic problems. Math. Program. 96(2), 293\u2013320 (2003)","journal-title":"Math. Program."},{"key":"1511_CR42","unstructured":"Potechin, A.: Sum of squares lower bounds from symmetry and a good story. arXiv:1711.11469 (2017)"},{"key":"1511_CR43","unstructured":"Potechin, A., Steurer, D.: Exact tensor completion with sum-of-squares. arXiv:1702.06237 (2017)"},{"key":"1511_CR44","unstructured":"Raghavendra, P., Schramm, T., Steurer, D.: High-dimensional estimation via sum-of-squares proofs. arXiv:1807.11419 (2018)"},{"issue":"2","key":"1511_CR45","doi-asserted-by":"publisher","first-page":"315","DOI":"10.1007\/s10107-017-1127-6","volume":"167","author":"A Raymond","year":"2018","unstructured":"Raymond, A., Saunderson, J., Singh, M., Thomas, R.R.: Symmetric sums of squares over k-subset hypercubes. Math. Program. 167(2), 315\u2013354 (2018)","journal-title":"Math. Program."},{"issue":"4","key":"1511_CR46","doi-asserted-by":"publisher","first-page":"1239","DOI":"10.2178\/jsl\/1203350785","volume":"72","author":"AA Razborov","year":"2007","unstructured":"Razborov, A.A.: Flag algebras. J. Symb. Log. 72(4), 1239\u20131282 (2007)","journal-title":"J. Symb. Log."},{"issue":"3","key":"1511_CR47","doi-asserted-by":"publisher","first-page":"946","DOI":"10.1137\/090747476","volume":"24","author":"AA Razborov","year":"2010","unstructured":"Razborov, A.A.: On 3-hypergraphs with forbidden 4-vertex configurations. SIAM J. Discrete Math. 24(3), 946\u2013963 (2010)","journal-title":"SIAM J. Discrete Math."},{"key":"1511_CR48","unstructured":"Rothvo\u00df, T.: The Lasserre hierarchy in approximation algorithms. Lecture notes for MAPSP (2013)"},{"key":"1511_CR49","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4757-6804-6","volume-title":"The Symmetric Group. Graduate Texts in Mathematics","author":"B Sagan","year":"2001","unstructured":"Sagan, B.: The Symmetric Group. Graduate Texts in Mathematics. Springer, New York (2001)"},{"key":"1511_CR50","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), pp. 593\u2013602 (2008)","DOI":"10.1109\/FOCS.2008.74"},{"issue":"3","key":"1511_CR51","doi-asserted-by":"publisher","first-page":"411","DOI":"10.1137\/0403036","volume":"3","author":"H Sherali","year":"1990","unstructured":"Sherali, H., Adams, W.: 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":"5","key":"1511_CR52","doi-asserted-by":"publisher","first-page":"1318","DOI":"10.1137\/110851201","volume":"41","author":"O Svensson","year":"2012","unstructured":"Svensson, O.: Santa claus schedules jobs on unrelated machines. SIAM J. Comput. 41(5), 1318\u20131341 (2012)","journal-title":"SIAM J. Comput."},{"key":"1511_CR53","doi-asserted-by":"crossref","unstructured":"Verdugo, V., Verschae, J.: Breaking symmetries to rescue sum of squares: the case of makespan scheduling. In: 20th International Conference on Integer Programming and Combinatorial Optimization (IPCO 2019), pp. 427\u2013441 (2019)","DOI":"10.1007\/978-3-030-17953-3_32"},{"key":"1511_CR54","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511921735","volume-title":"The Design of Approximation Algorithms","author":"D Williamson","year":"2011","unstructured":"Williamson, D., Shmoys, D.: The Design of Approximation Algorithms. Cambridge University Press, Cambridge (2011)"}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-020-01511-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10107-020-01511-3\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-020-01511-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,5,13]],"date-time":"2021-05-13T23:52:20Z","timestamp":1620949940000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10107-020-01511-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,5,14]]},"references-count":54,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2020,9]]}},"alternative-id":["1511"],"URL":"https:\/\/doi.org\/10.1007\/s10107-020-01511-3","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"value":"0025-5610","type":"print"},{"value":"1436-4646","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,5,14]]},"assertion":[{"value":"31 May 2019","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"22 April 2020","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"14 May 2020","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}