{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,9]],"date-time":"2024-09-09T04:41:58Z","timestamp":1725856918367},"publisher-location":"Cham","reference-count":27,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319334608"},{"type":"electronic","value":"9783319334615"}],"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-33461-5_13","type":"book-chapter","created":{"date-parts":[[2016,5,24]],"date-time":"2016-05-24T22:35:59Z","timestamp":1464129359000},"page":"152-163","source":"Crossref","is-referenced-by-count":1,"title":["Semidefinite and Linear Programming Integrality Gaps for Scheduling Identical Machines"],"prefix":"10.1007","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":[[2016,5,25]]},"reference":[{"doi-asserted-by":"crossref","unstructured":"Alekhnovich, M., Arora, S., Tourlakis, I.: Towards strong nonapproximability results in the Lov\u00e1sz-Schrijver hierarchy. In: STOC, pp. 294\u2013303 (2005)","key":"13_CR1","DOI":"10.1145\/1060590.1060634"},{"unstructured":"Alon, N., Azar, Y., Woeginger, G.J., Yadid, T.: Approximation schemes for scheduling. In: SODA, pp. 493\u2013500 (1997)","key":"13_CR2"},{"key":"13_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. Theor. Comput. 2, 19\u201351 (2006)","journal-title":"Theor. Comput."},{"doi-asserted-by":"crossref","unstructured":"Bansal, N.: Approximating independent sets in sparse graphs. In: SODA, pp. 1\u20138 (2015)","key":"13_CR4","DOI":"10.1137\/1.9781611973730.1"},{"doi-asserted-by":"crossref","unstructured":"Bansal, N., Srinivasan, A., Svensson, O.: Lift-and-round to improve weighted completion time on unrelated machines. CoRR, abs\/1511.07826 (2015)","key":"13_CR5","DOI":"10.1145\/2897518.2897572"},{"key":"13_CR6","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. Theor. Comput. 2, 65\u201390 (2006)","journal-title":"Theor. Comput."},{"unstructured":"Charikar, M.: On semidefinite programming relaxations for graph coloring and vertex cover. In: SODA, pp. 616\u2013620 (2002)","key":"13_CR7"},{"key":"13_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"256","DOI":"10.1007\/978-3-642-40104-6_23","volume-title":"Algorithms and Data Structures","author":"E Chlamt\u00e1\u010d","year":"2013","unstructured":"Chlamt\u00e1\u010d, E., Friggstad, Z., Georgiou, K.: Lift-and-project methods for set cover and Knapsack. In: Dehne, F., Solis-Oba, R., Sack, J.-R. (eds.) WADS 2013. LNCS, vol. 8037, pp. 256\u2013267. Springer, Heidelberg (2013)"},{"key":"13_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"124","DOI":"10.1007\/978-3-642-15369-3_10","volume-title":"Approximation, Randomization, and Combinatorial Optimization","author":"E Chlamtac","year":"2010","unstructured":"Chlamtac, E., Krauthgamer, R., Raghavendra, P.: Approximating sparsest cut in graphs of bounded treewidth. In: Serna, M., Shaltiel, R., Jansen, K., Rolim, J. (eds.) APPROX 2010. LNCS, vol. 6302, pp. 124\u2013137. Springer, Heidelberg (2010)"},{"key":"13_CR10","doi-asserted-by":"crossref","first-page":"139","DOI":"10.1007\/978-1-4614-0769-0_6","volume-title":"Handbook on Semidefinite, Conic and Polynomial Optimization","author":"E Chlamtac","year":"2012","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, New York (2012)"},{"unstructured":"Fernandez de la Vega, W., Mathieu, C.: Linear programming relaxations of maxcut. In: SODA, pp. 53\u201361 (2007)","key":"13_CR11"},{"key":"13_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-Schrijver relaxations for maximum independent set. SIAM J. Comput. 32, 345\u2013370 (2003)","journal-title":"SIAM J. Comput."},{"key":"13_CR13","doi-asserted-by":"crossref","first-page":"499","DOI":"10.1145\/322077.322090","volume":"25","author":"MR Garey","year":"1978","unstructured":"Garey, M.R., Johnson, D.S.: \u201cStrong\u201d NP-completeness results: motivation, examples, and implications. J. ACM 25, 499\u2013508 (1978)","journal-title":"J. ACM"},{"key":"13_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-Schrijver hierarchy. SIAM J. Comput. 39, 3553\u20133570 (2010)","journal-title":"SIAM J. Comput."},{"key":"13_CR15","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 $$ for the chromatic number of a graph. SIAM J. Optim. 19, 572\u2013591 (2008)","journal-title":"SIAM J. Optim."},{"key":"13_CR16","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":"13_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"853","DOI":"10.1007\/978-3-662-48350-3_71","volume-title":"Algorithms \u2013 ESA 2015","author":"Adam Kurpisz","year":"2015","unstructured":"Kurpisz, Adam, Lepp\u00e4nen, S., Mastrolilli, M.: A Lasserre lower bound for the min-sum single machine scheduling problem. In: Bansal, N., Finocchi, I. (eds.) ESA 2015. LNCS, vol. 9294, pp. 853\u2013864. Springer, Heidelberg (2015). doi: 10.1007\/978-3-662-48350-3_71"},{"key":"13_CR18","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":"13_CR19","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, 470\u2013496 (2003)","journal-title":"Math. Oper. Res."},{"unstructured":"Levey, E., Rothvoss, T.: A Lasserre-based $$(1+\\varepsilon )$$ -approximation for $$\\text{P}m | p_j=1, \\text{ prec } | \\text{ C }_{\\max }$$ . CoRR, abs\/1509.07808 (2015)","key":"13_CR20"},{"key":"13_CR21","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":"13_CR22","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."},{"unstructured":"Rothvo\u00df, T.: The Lasserre hierarchy in approximation algorithms. Lecture notes for the MAPSP (2013)","key":"13_CR23"},{"doi-asserted-by":"crossref","unstructured":"Schoenebeck, G., Trevisan, L., Tulsiani, M.: Tight integrality gaps for Lov\u00e1sz-Schrijver 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)","key":"13_CR24","DOI":"10.1145\/1250790.1250836"},{"key":"13_CR25","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":"13_CR26","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":"13_CR27","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, New York (2011)"}],"container-title":["Lecture Notes in Computer Science","Integer Programming and Combinatorial Optimization"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-33461-5_13","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,9,8]],"date-time":"2019-09-08T19:46:34Z","timestamp":1567971994000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-33461-5_13"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016]]},"ISBN":["9783319334608","9783319334615"],"references-count":27,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-33461-5_13","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2016]]}}}