{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:41:01Z","timestamp":1740109261231,"version":"3.37.3"},"reference-count":24,"publisher":"Springer Science and Business Media LLC","issue":"12","license":[{"start":{"date-parts":[[2018,3,28]],"date-time":"2018-03-28T00:00:00Z","timestamp":1522195200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100003977","name":"Israel Science Foundation","doi-asserted-by":"publisher","award":["1002\/14"],"award-info":[{"award-number":["1002\/14"]}],"id":[{"id":"10.13039\/501100003977","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100002790","name":"Canadian Network for Research and Innovation in Machining Technology, Natural Sciences and Engineering Research Council of Canada","doi-asserted-by":"publisher","award":["Discovery grant"],"award-info":[{"award-number":["Discovery grant"]}],"id":[{"id":"10.13039\/501100002790","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001804","name":"Canada Research Chairs","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100001804","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100002790","name":"Canadian Network for Research and Innovation in Machining Technology, Natural Sciences and Engineering Research Council of Canada","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100002790","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2018,12]]},"DOI":"10.1007\/s00453-018-0427-4","type":"journal-article","created":{"date-parts":[[2018,3,28]],"date-time":"2018-03-28T08:34:09Z","timestamp":1522226049000},"page":"3920-3942","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Lift-and-Project Methods for Set Cover and Knapsack"],"prefix":"10.1007","volume":"80","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-0296-0107","authenticated-orcid":false,"given":"Eden","family":"Chlamt\u00e1\u010d","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Zachary","family":"Friggstad","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Konstantinos","family":"Georgiou","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2018,3,28]]},"reference":[{"doi-asserted-by":"crossref","unstructured":"Alekhnovich, M., Arora, S., Tourlakis, I.: Towards strong nonapproximability results in the Lov\u00e1sz-Schrijver hierarchy. In: Proceedings of ACM Symposium on Theory of Computing, pp. 294\u2013303 (2005)","key":"427_CR1","DOI":"10.1145\/1060590.1060634"},{"issue":"1","key":"427_CR2","doi-asserted-by":"publisher","first-page":"411","DOI":"10.1137\/130950173","volume":"30","author":"YH Au","year":"2016","unstructured":"Au, Y.H., Tun\u00e7el, L.: A comprehensive analysis of polyhedral lift-and-project methods. SIAM J. Discrete Math. 30(1), 411\u2013451 (2016)","journal-title":"SIAM J. Discrete Math."},{"doi-asserted-by":"crossref","unstructured":"Barak, B., Raghavendra, P., Steurer, D.: Rounding semidefinite programming hierarchies via global correlation. In: Proceedings of IEEE Symposium on Foundations of Computer Science, pp. 472 \u2013481 (2011)","key":"427_CR3","DOI":"10.1109\/FOCS.2011.95"},{"doi-asserted-by":"crossref","unstructured":"Barak, B., Brandao, F.G., Harrow, A.W., Kelner, J., Steurer, D., Zhou, Y.: Hypercontractivity, sum-of-squares proofs, and their applications. In: Proceedings of the Forty-fourth Annual ACM Symposium on Theory of Computing, STOC \u201912, pp. 307\u2013326. ACM, New York (2012)","key":"427_CR4","DOI":"10.1145\/2213977.2214006"},{"issue":"3","key":"427_CR5","doi-asserted-by":"publisher","first-page":"713","DOI":"10.1137\/S0097539700382820","volume":"35","author":"C Chekuri","year":"2005","unstructured":"Chekuri, C., Khanna, S.: A polynomial time approximation scheme for the multiple knapsack problem. SIAM J. Comput. 35(3), 713\u2013728 (2005)","journal-title":"SIAM J. Comput."},{"key":"427_CR6","first-page":"256","volume-title":"Lecture Notes in Computer Science","author":"Eden Chlamt\u00e1\u010d","year":"2013","unstructured":"Chlamt\u00e1\u010d, E., Friggstad, Z., Georgiou, K.: Lift-and-project methods for set cover and knapsack. In: Proceedings of Algorithms and Data Structures: 13th International Symposium, WADS \u201913, pp. 256\u2013267 (2014)"},{"key":"427_CR7","series-title":"Conic and polynomial optimization, vol. 166 of international series in operations research and management science","first-page":"139","volume-title":"Handbook on Semidefinite","author":"E Chlamt\u00e1\u010d","year":"2012","unstructured":"Chlamt\u00e1\u010d, E., Tulsiani, M.: Convex relaxations and integrality gaps. In: Anjos, M.F., Lasserre, J.B. (eds.) Handbook on Semidefinite. Conic and polynomial optimization, vol. 166 of international series in operations research and management science, pp. 139\u2013169. Springer, USA (2012)"},{"issue":"3","key":"427_CR8","doi-asserted-by":"publisher","first-page":"233","DOI":"10.1287\/moor.4.3.233","volume":"4","author":"V Chv\u00e1tal","year":"1979","unstructured":"Chv\u00e1tal, V.: A greedy heuristic for the set-covering problem. Math. Oper. Res. 4(3), 233\u2013235 (1979)","journal-title":"Math. Oper. Res."},{"issue":"16","key":"427_CR9","doi-asserted-by":"publisher","first-page":"957","DOI":"10.1016\/j.ipl.2009.05.003","volume":"109","author":"M Cygan","year":"2009","unstructured":"Cygan, M., Kowalik, L., Wykurz, M.: Exponential-time approximation of weighted set cover. Inf. Process. Lett. 109(16), 957\u2013961 (2009)","journal-title":"Inf. Process. Lett."},{"doi-asserted-by":"crossref","unstructured":"Dinur, I., Steurer, D.: Analytical approach to parallel repetition. In: Proceedings of the 46th Annual ACM Symposium on Theory of Computing, STOC \u201914. ACM, New York, pp. 624\u2013633 (2014)","key":"427_CR10","DOI":"10.1145\/2591796.2591884"},{"issue":"4","key":"427_CR11","doi-asserted-by":"publisher","first-page":"634","DOI":"10.1145\/285055.285059","volume":"45","author":"U Feige","year":"1998","unstructured":"Feige, U.: A threshold of \n                    \n                      \n                    \n                    $$\\ln n$$\n                    \n                      \n                        \n                          ln\n                          n\n                        \n                      \n                    \n                   for approximating set cover. J. ACM 45(4), 634\u2013652 (1998)","journal-title":"J. ACM"},{"doi-asserted-by":"crossref","unstructured":"Guruswami, V., Sinop, A.K.: Lasserre hierarchy, higher eigenvalues, and approximation schemes for graph partitioning and quadratic integer programming with PSD objectives. In: Proceedings of IEEE Symposium on Foundations of Computer Science, pp. 482 \u2013491 (2011)","key":"427_CR12","DOI":"10.1109\/FOCS.2011.36"},{"issue":"4","key":"427_CR13","doi-asserted-by":"publisher","first-page":"463","DOI":"10.1145\/321906.321909","volume":"22","author":"OH Ibarra","year":"1975","unstructured":"Ibarra, O.H., Kim, C.E.: Fast approximation algorithms for the knapsack and sum of subset problems. J. ACM 22(4), 463\u2013468 (1975)","journal-title":"J. ACM"},{"issue":"3","key":"427_CR14","doi-asserted-by":"publisher","first-page":"256","DOI":"10.1016\/S0022-0000(74)80044-9","volume":"9","author":"DS Johnson","year":"1974","unstructured":"Johnson, D.S.: Approximation algorithms for combinatorial problems. J. Comput. Syst. Sci. 9(3), 256\u2013278 (1974)","journal-title":"J. Comput. Syst. Sci."},{"key":"427_CR15","doi-asserted-by":"publisher","first-page":"301","DOI":"10.1007\/978-3-642-20807-2_24","volume-title":"Integer Programming and Combinatoral Optimization","author":"Anna R. Karlin","year":"2011","unstructured":"Karlin, A., Mathieu, C., Nguyen, C.: Integrality gaps of linear and semi-definite programming relaxations for knapsack. In: Proceedings of Conference on Integer Programming and Combinatoral Optimization, pp. 301\u2013314 (2011)"},{"key":"427_CR16","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1007\/978-1-4684-2001-2_9","volume-title":"Complexity of Computer Computations","author":"Richard M. Karp","year":"1972","unstructured":"Karp, R.M.: Reducibility among combinatorial problems. In: Complexity of Computer Computations, pp. 85\u2013103 (1972)"},{"issue":"3","key":"427_CR17","doi-asserted-by":"publisher","first-page":"756","DOI":"10.1137\/S1052623400380079","volume":"12","author":"JB Lasserre","year":"2002","unstructured":"Lasserre, J.B.: An explicit equivalent positive semidefinite program for nonlinear 0\u20131 programs. SIAM J. Optim. 12(3), 756\u2013769 (2002)","journal-title":"SIAM J. Optim."},{"issue":"3","key":"427_CR18","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\u2013Adams, Lov\u00e1sz\u2013Schrijver, and Lasserre relaxations for 0\u20131 programming. Math. Oper. Res. 28(3), 470\u2013496 (2003)","journal-title":"Math. Oper. Res."},{"issue":"4","key":"427_CR19","doi-asserted-by":"publisher","first-page":"383","DOI":"10.1016\/0012-365X(75)90058-8","volume":"13","author":"L Lov\u00e1sz","year":"1975","unstructured":"Lov\u00e1sz, L.: On the ratio of optimal integral and fractional covers. Discrete Math. 13(4), 383\u2013390 (1975)","journal-title":"Discrete Math."},{"issue":"2","key":"427_CR20","doi-asserted-by":"publisher","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(2), 166\u2013190 (1991)","journal-title":"SIAM J. Optim."},{"key":"427_CR21","doi-asserted-by":"publisher","first-page":"1537","DOI":"10.1137\/1.9781611973105.111","volume-title":"Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms","author":"Ryan O'Donnell","year":"2013","unstructured":"O\u2019Donnell, R., Zhou, Y.: Approximability and proof complexity. In: Proceedings of the Twenty-fourth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA \u201913. Society for Industrial and Applied Mathematics, Philadelphia, pp. 1537\u20131556 (2013)"},{"doi-asserted-by":"crossref","unstructured":"Raghavendra, P.: Optimal algorithms and inapproximability results for every CSP? In: Proceedings of ACM Symposium on Theory of Computing, pp. 245\u2013254 (2008)","key":"427_CR22","DOI":"10.1145\/1374376.1374414"},{"doi-asserted-by":"crossref","unstructured":"Raghavendra, P., Tan, N.: Approximating CSPs with global cardinality constraints using SDP hierarchies. In: Proceedings of ACM-SIAM Symposium on Discrete Algorithms, pp. 373\u2013387. SIAM (2012)","key":"427_CR23","DOI":"10.1137\/1.9781611973099.33"},{"issue":"3","key":"427_CR24","doi-asserted-by":"publisher","first-page":"411","DOI":"10.1137\/0403036","volume":"3","author":"HD Sherali","year":"1990","unstructured":"Sherali, H.D., Adams, W.P.: 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."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-018-0427-4\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-018-0427-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-018-0427-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,3,27]],"date-time":"2019-03-27T20:06:35Z","timestamp":1553717195000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-018-0427-4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,3,28]]},"references-count":24,"journal-issue":{"issue":"12","published-print":{"date-parts":[[2018,12]]}},"alternative-id":["427"],"URL":"https:\/\/doi.org\/10.1007\/s00453-018-0427-4","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2018,3,28]]},"assertion":[{"value":"6 October 2016","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"15 March 2018","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"28 March 2018","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}