{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,8]],"date-time":"2024-09-08T20:55:48Z","timestamp":1725828948146},"publisher-location":"Berlin, Heidelberg","reference-count":24,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783662483497"},{"type":"electronic","value":"9783662483503"}],"license":[{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"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":[[2015]]},"DOI":"10.1007\/978-3-662-48350-3_71","type":"book-chapter","created":{"date-parts":[[2015,8,31]],"date-time":"2015-08-31T21:40:34Z","timestamp":1441057234000},"page":"853-864","source":"Crossref","is-referenced-by-count":3,"title":["A Lasserre Lower Bound for the Min-Sum Single Machine Scheduling Problem"],"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":[[2015,11,12]]},"reference":[{"key":"71_CR1","doi-asserted-by":"crossref","unstructured":"Bansal, N., Pruhs, K.: The geometry of scheduling. In: FOCS, pp. 407\u2013414 (2010)","DOI":"10.1109\/FOCS.2010.46"},{"key":"71_CR2","doi-asserted-by":"crossref","unstructured":"Barak, B., Chan, S.O., Kothari, P.: Sum of squares lower bounds from pairwise independence. In: STOC (2015)","DOI":"10.1145\/2746539.2746625"},{"key":"71_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-subgraph. In: SODA, pp. 388\u2013405 (2012)","DOI":"10.1137\/1.9781611973099.34"},{"key":"71_CR4","unstructured":"Carr, R.D., Fleischer, L., Leung, V.J., Phillips, C.A.: Strengthening integrality gaps for capacitated network design and covering problems. In: SODA, pp. 106\u2013115 (2000)"},{"key":"71_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"135","DOI":"10.1007\/978-3-642-22935-0_12","volume-title":"Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques","author":"M. Cheung","year":"2011","unstructured":"Cheung, M., Shmoys, D.B.: A primal-dual approximation algorithm for min-sum single-machine scheduling problems. In: Goldberg, L.A., Jansen, K., Ravi, R., Rolim, J.D.P. (eds.) RANDOM 2011 and APPROX 2011. LNCS, vol.\u00a06845, pp. 135\u2013146. Springer, Heidelberg (2011)"},{"key":"71_CR6","unstructured":"Chlamtac, E., Tulsiani, M.: Convex relaxations and integrality gaps. In: Handbook on Semidefinite, Conic and Polynomial Optimization. Springer (to appear)"},{"key":"71_CR7","doi-asserted-by":"crossref","unstructured":"Fawzi, H., Saunderson, J., Parrilo, P.: Sparse sum-of-squares certificates on finite abelian groups. CoRR, abs\/1503.01207 (2015)","DOI":"10.1109\/CDC.2015.7403148"},{"issue":"2","key":"71_CR8","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. Computational Complexity\u00a010(2), 139\u2013154 (2001)","journal-title":"Computational Complexity"},{"issue":"1-2","key":"71_CR9","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. Theoretical Computer Science\u00a0259(1-2), 613\u2013622 (2001)","journal-title":"Theoretical Computer Science"},{"key":"71_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"301","DOI":"10.1007\/978-3-642-20807-2_24","volume-title":"Integer Programming and Combinatoral Optimization","author":"A.R. 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.\u00a06655, pp. 301\u2013314. Springer, Heidelberg (2011)"},{"key":"71_CR11","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1007\/978-1-4684-2001-2_9","volume-title":"Proceedings of a symposium on the Complexity of Computer Computations","author":"R.M. Karp","year":"1972","unstructured":"Karp, R.M.: Reducibility among combinatorial problems. In: Proceedings of a symposium on the Complexity of Computer Computations, March 20-22, pp. 85\u2013103. Thomas J. Watson Research Center, Yorktown Heights (1972)"},{"key":"71_CR12","doi-asserted-by":"crossref","unstructured":"Kurpisz, A., Lepp\u00e4nen, S., Mastrolilli, M.: On the hardest problem formulations for the 0\/1 Lasserre hierarchy. In: Halld\u00f3rsson, M M., Iwama, K., Kobayashi, N., Speckmann, B. (eds.) ICALP 2015. LNCS, vol.\u00a09134, pp. 872\u2013885. Springer, Heidelberg (2015)","DOI":"10.1007\/978-3-662-47672-7_71"},{"issue":"3","key":"71_CR13","doi-asserted-by":"publisher","first-page":"796","DOI":"10.1137\/S1052623400366802","volume":"11","author":"J.B. Lasserre","year":"2001","unstructured":"Lasserre, J.B.: Global optimization with polynomials and the problem of moments. SIAM Journal on Optimization\u00a011(3), 796\u2013817 (2001)","journal-title":"SIAM Journal on Optimization"},{"issue":"3","key":"71_CR14","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-1 programming. Mathematics of Operations Research\u00a028(3), 470\u2013496 (2003)","journal-title":"Mathematics of Operations Research"},{"key":"71_CR15","doi-asserted-by":"crossref","unstructured":"Meka, R., Potechin, A., Wigderson, A.: Sum-of-squares lower bounds for planted clique. CoRR, abs\/1503.06447. In: STOC 2015 (2015) (to appear)","DOI":"10.1145\/2746539.2746600"},{"key":"71_CR16","unstructured":"Mestre, J., Verschae, J.: A 4-approximation for scheduling on a single machine with general cost function. CoRR, abs\/1403.0298 (2014)"},{"key":"71_CR17","doi-asserted-by":"publisher","first-page":"102","DOI":"10.1287\/mnsc.15.1.102","volume":"15","author":"M.J. Moore","year":"1968","unstructured":"Moore, M.J.: An n job, one machine sequencing algorithm for minimizing the number of late jobs. Management Science\u00a015, 102\u2013109 (1968)","journal-title":"Management Science"},{"key":"71_CR18","doi-asserted-by":"crossref","unstructured":"O\u2019Donnell, R., Zhou, Y.: Approximability and proof complexity. In: Khanna, S. (ed.) SODA, pp. 1537\u20131556. SIAM (2013)","DOI":"10.1137\/1.9781611973105.111"},{"key":"71_CR19","unstructured":"Parrilo, P.: Structured Semidefinite Programs and Semialgebraic Geometry Methods in Robustness and Optimization. PhD thesis, California Institute of Technology (2000)"},{"key":"71_CR20","unstructured":"Rothvo\u00df, T.: The lasserre hierarchy in approximation algorithms. Lecture Notes for the MAPSP 2013 - Tutorial (June 2013)"},{"key":"71_CR21","doi-asserted-by":"crossref","unstructured":"Schoenebeck, G.: Linear level Lasserre lower bounds for certain k-csps. In: FOCS, pp. 593\u2013602 (2008)","DOI":"10.1109\/FOCS.2008.74"},{"issue":"6","key":"71_CR22","doi-asserted-by":"publisher","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\u00a023(6), 731\u2013734 (1987)","journal-title":"Cybernetics"},{"key":"71_CR23","doi-asserted-by":"crossref","unstructured":"Tulsiani, M.: Csp gaps and reductions in the Lasserre hierarchy. In: STOC, pp. 303\u2013312 (2009)","DOI":"10.1145\/1536414.1536457"},{"key":"71_CR24","doi-asserted-by":"publisher","first-page":"168","DOI":"10.1007\/BF01580441","volume":"8","author":"L.A. Wolsey","year":"1975","unstructured":"Wolsey, L.A.: Facets for a linear inequality in 0\u20131 variables. Mathematical Programming\u00a08, 168\u2013175 (1975)","journal-title":"Mathematical Programming"}],"container-title":["Lecture Notes in Computer Science","Algorithms - ESA 2015"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-662-48350-3_71","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,30]],"date-time":"2019-05-30T16:03:53Z","timestamp":1559232233000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-662-48350-3_71"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015]]},"ISBN":["9783662483497","9783662483503"],"references-count":24,"URL":"https:\/\/doi.org\/10.1007\/978-3-662-48350-3_71","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2015]]}}}