{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,14]],"date-time":"2025-10-14T10:45:25Z","timestamp":1760438725190,"version":"3.37.3"},"reference-count":30,"publisher":"Springer Science and Business Media LLC","issue":"1-2","license":[{"start":{"date-parts":[[2017,5,10]],"date-time":"2017-05-10T00:00:00Z","timestamp":1494374400000},"content-version":"tdm","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":["Project 200020-144491\/1 \u201cApproximation Algorithms for Machine Scheduling Through Theory and Experiments\u201d"],"award-info":[{"award-number":["Project 200020-144491\/1 \u201cApproximation Algorithms for Machine Scheduling Through Theory and Experiments\u201d"]}],"id":[{"id":"10.13039\/501100001711","id-type":"DOI","asserted-by":"crossref"}]},{"name":"Conicyt","award":["CONICYT-PCHA\/Doctorado Nacional\/2014-21140930"],"award-info":[{"award-number":["CONICYT-PCHA\/Doctorado Nacional\/2014-21140930"]}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Math. Program."],"published-print":{"date-parts":[[2018,11]]},"DOI":"10.1007\/s10107-017-1152-5","type":"journal-article","created":{"date-parts":[[2017,5,10]],"date-time":"2017-05-10T10:47:55Z","timestamp":1494413275000},"page":"231-248","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["Semidefinite and linear programming integrality gaps for scheduling identical machines"],"prefix":"10.1007","volume":"172","author":[{"given":"Adam","family":"Kurpisz","sequence":"first","affiliation":[]},{"given":"Monaldo","family":"Mastrolilli","sequence":"additional","affiliation":[]},{"given":"Claire","family":"Mathieu","sequence":"additional","affiliation":[]},{"given":"Tobias","family":"M\u00f6mke","sequence":"additional","affiliation":[]},{"given":"Victor","family":"Verdugo","sequence":"additional","affiliation":[]},{"given":"Andreas","family":"Wiese","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2017,5,10]]},"reference":[{"key":"1152_CR1","doi-asserted-by":"crossref","unstructured":"Alekhnovich, M., Arora, S., Tourlakis, I.: Towards strong nonapproximability results in the Lov\u00e1sz\u2013Schrijver hierarchy. In: STOC, pp. 294\u2013303 (2005)","DOI":"10.1145\/1060590.1060634"},{"key":"1152_CR2","unstructured":"Alon, N., Azar, Y., Woeginger, G.J., Yadid, T.: Approximation schemes for scheduling. In: SODA, pp. 493\u2013500 (1997)"},{"key":"1152_CR3","doi-asserted-by":"crossref","first-page":"19","DOI":"10.4086\/toc.2006.v002a002","volume":"2","author":"S Arora","year":"2006","unstructured":"Arora, S., Bollob\u00e1s, B., Lov\u00e1sz, L., Tourlakis, I.: Proving integrality gaps without knowing the linear program. Theory Comput. 2, 19\u201351 (2006)","journal-title":"Theory Comput."},{"issue":"2","key":"1152_CR4","doi-asserted-by":"crossref","first-page":"5","DOI":"10.1145\/1502793.1502794","volume":"56","author":"S Arora","year":"2009","unstructured":"Arora, S., Rao, S., Vazirani, U.: Expander flows, geometric embeddings and graph partitioning. J. ACM 56(2), 5 (2009)","journal-title":"J. ACM"},{"key":"1152_CR5","doi-asserted-by":"crossref","unstructured":"Bansal, N.: Approximating independent sets in sparse graphs. In: SODA, pp. 1\u20138 (2015)","DOI":"10.1137\/1.9781611973730.1"},{"key":"1152_CR6","doi-asserted-by":"crossref","unstructured":"Bansal, N., Srinivasan, A., Svensson, O.: Lift-and-round to improve weighted completion time on unrelated machines. CoRR arXiv:1511.07826 (2015)","DOI":"10.1145\/2897518.2897572"},{"key":"1152_CR7","doi-asserted-by":"crossref","first-page":"65","DOI":"10.4086\/toc.2006.v002a004","volume":"2","author":"J Buresh-Oppenheim","year":"2006","unstructured":"Buresh-Oppenheim, J., Galesi, N., Hoory, S., Magen, A., Pitassi, T.: Rank bounds and integrality gaps for cutting planes procedures. Theory Comput. 2, 65\u201390 (2006)","journal-title":"Theory Comput."},{"key":"1152_CR8","doi-asserted-by":"crossref","unstructured":"Chan, S.O., Lee, J., Raghavendra, P., Steurer, D.: Approximate constraint satisfaction requires large lp relaxations. In: FOCS, pp. 350\u2013359. IEEE (2013)","DOI":"10.1109\/FOCS.2013.45"},{"key":"1152_CR9","unstructured":"Charikar, M.: On semidefinite programming relaxations for graph coloring and vertex cover. In: SODA, pp. 616\u2013620 (2002)"},{"key":"1152_CR10","doi-asserted-by":"crossref","unstructured":"Chlamtac, E., Friggstad, Z., Georgiou, K.: Lift-and-project methods for set cover and knapsack. In: Algorithms and Data Structures, pp. 256\u2013267 (2013)","DOI":"10.1007\/978-3-642-40104-6_23"},{"key":"1152_CR11","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, Berlin (2012)","DOI":"10.1007\/978-1-4614-0769-0_6"},{"key":"1152_CR12","doi-asserted-by":"crossref","first-page":"345","DOI":"10.1137\/S009753970240118X","volume":"32","author":"U Feige","year":"2003","unstructured":"Feige, U., Krauthgamer, R.: The probable value of the Lov\u00e1sz\u2013Schrijver relaxations for maximum independent set. SIAM J. Comput. 32, 345\u2013370 (2003)","journal-title":"SIAM J. Comput."},{"key":"1152_CR13","doi-asserted-by":"crossref","first-page":"499","DOI":"10.1145\/322077.322090","volume":"25","author":"M Garey","year":"1978","unstructured":"Garey, M., Johnson, D.: \u201cStrong\u201d NP-completeness results: motivation, examples, and implications. J. ACM 25, 499\u2013508 (1978)","journal-title":"J. ACM"},{"key":"1152_CR14","doi-asserted-by":"crossref","first-page":"3553","DOI":"10.1137\/080721479","volume":"39","author":"K Georgiou","year":"2010","unstructured":"Georgiou, K., Magen, A., Pitassi, T., Tourlakis, I.: Integrality gaps of 2-o(1) for vertex cover SDPs in the Lov\u00e1sz\u2013Schrijver hierarchy. SIAM J. Comput. 39, 3553\u20133570 (2010)","journal-title":"SIAM J. Comput."},{"key":"1152_CR15","doi-asserted-by":"crossref","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. J. ACM 42, 1115\u20131145 (1995)","journal-title":"J. ACM"},{"key":"1152_CR16","doi-asserted-by":"crossref","first-page":"572","DOI":"10.1137\/050648237","volume":"19","author":"N Gvozdenovic","year":"2008","unstructured":"Gvozdenovic, N., Laurent, M.: The operator $$\\psi $$ \u03c8 for the chromatic number of a graph. SIAM J. Optim. 19, 572\u2013591 (2008)","journal-title":"SIAM J. Optim."},{"key":"1152_CR17","doi-asserted-by":"crossref","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. J. ACM 34, 144\u2013162 (1987)","journal-title":"J. ACM"},{"key":"1152_CR18","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9781139020411","volume-title":"Matrix Analysis","author":"RA Horn","year":"2012","unstructured":"Horn, R.A., Johnson, C.R.: Matrix Analysis. Cambridge University Press, Cambridge (2012)"},{"key":"1152_CR19","first-page":"853","volume":"2015","author":"A Kurpisz","year":"2015","unstructured":"Kurpisz, A., Lepp\u00e4nen, S., Mastrolilli, M.: A Lasserre lower bound for the min-sum single machine scheduling problem. Algorithms ESA 2015, 853\u2013864 (2015)","journal-title":"Algorithms ESA"},{"key":"1152_CR20","doi-asserted-by":"crossref","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":"1152_CR21","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\u2013Schrijver, and Lasserre relaxations for 0\u20131 programming. Math. Oper. Res. 28, 470\u2013496 (2003)","journal-title":"Math. Oper. Res."},{"key":"1152_CR22","unstructured":"Levey, E., Rothvoss, T.: A Lasserre-based $$(1+\\varepsilon )$$ ( 1 + \u03b5 ) -approximation for $$\\text{P}m | p_j=1, \\text{ prec } | \\text{ C }_{\\max }$$ P m | p j = 1 , prec | C max . CoRR arXiv:1509.07808 (2015)"},{"key":"1152_CR23","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, 166\u2013190 (1991)","journal-title":"SIAM J. Optim."},{"key":"1152_CR24","doi-asserted-by":"crossref","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, 293\u2013320 (2003)","journal-title":"Math. Program."},{"key":"1152_CR25","unstructured":"Rothvo\u00df, T.: The lasserre hierarchy in approximation algorithms. Lecture notes for the MAPSP (2013)"},{"key":"1152_CR26","doi-asserted-by":"crossref","unstructured":"Schoenebeck, G., Trevisan, L., Tulsiani, M.: Tight integrality gaps for Lov\u00e1sz\u2013Schrijver LP relaxations of vertex cover and max cut. In: Proceedings of the Thirty-ninth Annual ACM Symposium on Theory of Computing, pp. 302\u2013310 (2007)","DOI":"10.1145\/1250790.1250836"},{"key":"1152_CR27","doi-asserted-by":"crossref","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, 411\u2013430 (1990)","journal-title":"SIAM J. Discrete Math."},{"key":"1152_CR28","unstructured":"de\u00a0la Vega, W.F., Mathieu, C.: Linear programming relaxations of maxcut. In: SODA, pp. 53\u201361 (2007)"},{"key":"1152_CR29","doi-asserted-by":"crossref","first-page":"371","DOI":"10.1007\/s10951-013-0359-4","volume":"17","author":"J Verschae","year":"2014","unstructured":"Verschae, J., Wiese, A.: On the configuration-LP for scheduling on unrelated machines. J. Sched. 17, 371\u2013383 (2014)","journal-title":"J. Sched."},{"key":"1152_CR30","doi-asserted-by":"crossref","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":"http:\/\/link.springer.com\/article\/10.1007\/s10107-017-1152-5\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-017-1152-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-017-1152-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,9,24]],"date-time":"2019-09-24T02:50:43Z","timestamp":1569293443000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10107-017-1152-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,5,10]]},"references-count":30,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2018,11]]}},"alternative-id":["1152"],"URL":"https:\/\/doi.org\/10.1007\/s10107-017-1152-5","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"type":"print","value":"0025-5610"},{"type":"electronic","value":"1436-4646"}],"subject":[],"published":{"date-parts":[[2017,5,10]]}}}