{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,7]],"date-time":"2024-09-07T20:21:58Z","timestamp":1725740518115},"publisher-location":"Berlin, Heidelberg","reference-count":19,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642401039"},{"type":"electronic","value":"9783642401046"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2013]]},"DOI":"10.1007\/978-3-642-40104-6_23","type":"book-chapter","created":{"date-parts":[[2013,7,11]],"date-time":"2013-07-11T05:36:30Z","timestamp":1373520990000},"page":"256-267","source":"Crossref","is-referenced-by-count":1,"title":["Lift-and-Project Methods for Set Cover and Knapsack"],"prefix":"10.1007","author":[{"given":"Eden","family":"Chlamt\u00e1\u010d","sequence":"first","affiliation":[]},{"given":"Zachary","family":"Friggstad","sequence":"additional","affiliation":[]},{"given":"Konstantinos","family":"Georgiou","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"23_CR1","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)","DOI":"10.1145\/1060590.1060634"},{"key":"23_CR2","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)","DOI":"10.1109\/FOCS.2011.95"},{"key":"23_CR3","series-title":"International Series in Operations Research & Management Science","doi-asserted-by":"publisher","first-page":"139","DOI":"10.1007\/978-1-4614-0769-0_6","volume-title":"Handbook on Semidefinite, Conic and Polynomial Optimization","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. International Series in Operations Research & Management Science, vol.\u00a0166, pp. 139\u2013169. Springer, Heidelberg (2012)"},{"issue":"3","key":"23_CR4","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. Mathematics of Operations Research\u00a04(3), 233\u2013235 (1979), doi:10.2307\/3689577","journal-title":"Mathematics of Operations Research"},{"issue":"16","key":"23_CR5","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.\u00a0109(16), 957\u2013961 (2009)","journal-title":"Inf. Process. Lett."},{"issue":"4","key":"23_CR6","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 ln n for approximating set cover. J. ACM\u00a045(4), 634\u2013652 (1998)","journal-title":"J. ACM"},{"key":"23_CR7","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 (October 2011)","DOI":"10.1109\/FOCS.2011.36"},{"issue":"4","key":"23_CR8","doi-asserted-by":"publisher","first-page":"463","DOI":"10.1145\/321906.321909","volume":"22","author":"O.H. Ibarra","year":"1975","unstructured":"Ibarra, O.H., Kim, C.E.: Fast approximation algorithms for the knapsack and sum of subset problems. J. ACM\u00a022(4), 463\u2013468 (1975)","journal-title":"J. ACM"},{"issue":"2","key":"23_CR9","doi-asserted-by":"publisher","first-page":"367","DOI":"10.1006\/jcss.2000.1727","volume":"62","author":"R. Impagliazzo","year":"2001","unstructured":"Impagliazzo, R., Paturi, R.: On the complexity of k-SAT. J. Comput. Syst. Sci.\u00a062(2), 367\u2013375 (2001)","journal-title":"J. Comput. Syst. Sci."},{"issue":"3","key":"23_CR10","doi-asserted-by":"publisher","first-page":"256","DOI":"10.1016\/S0022-0000(74)80044-9","volume":"9","author":"D.S. Johnson","year":"1974","unstructured":"Johnson, D.S.: Approximation algorithms for combinatorial problems. J. Comput. Syst. Sci.\u00a09(3), 256\u2013278 (1974)","journal-title":"J. Comput. Syst. Sci."},{"key":"23_CR11","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":"23_CR12","doi-asserted-by":"crossref","unstructured":"Karp, R.M.: Reducibility among combinatorial problems. In: Complexity of Computer Computations, pp. 85\u2013103 (1972)","DOI":"10.1007\/978-1-4684-2001-2_9"},{"issue":"3","key":"23_CR13","doi-asserted-by":"publisher","first-page":"756","DOI":"10.1137\/S1052623400380079","volume":"12","author":"J.B. Lasserre","year":"2002","unstructured":"Lasserre, J.B.: An explicit equivalent positive semidefinite program for nonlinear 0-1 programs. SIAM Journal on Optimization\u00a012(3), 756\u2013769 (2002)","journal-title":"SIAM Journal on Optimization"},{"issue":"4","key":"23_CR14","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 Mathematics\u00a013(4), 383\u2013390 (1975)","journal-title":"Discrete Mathematics"},{"issue":"2","key":"23_CR15","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-1 optimization. SIAM J. Optim.\u00a01(2), 166\u2013190 (1991)","journal-title":"SIAM J. Optim."},{"key":"23_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"276","DOI":"10.1007\/978-3-642-32512-0_24","volume-title":"Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques","author":"D. Moshkovitz","year":"2012","unstructured":"Moshkovitz, D.: The projection games conjecture and the NP-hardness of ln n-approximating set-cover. In: Gupta, A., Jansen, K., Rolim, J., Servedio, R. (eds.) APPROX 2012 and RANDOM 2012. LNCS, vol.\u00a07408, pp. 276\u2013287. Springer, Heidelberg (2012)"},{"key":"23_CR17","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)","DOI":"10.1145\/1374376.1374414"},{"key":"23_CR18","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)","DOI":"10.1137\/1.9781611973099.33"},{"issue":"3","key":"23_CR19","doi-asserted-by":"publisher","first-page":"411","DOI":"10.1137\/0403036","volume":"3","author":"H.D. 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 Journal on Discrete Mathematics\u00a03(3), 411\u2013430 (1990)","journal-title":"SIAM Journal on Discrete Mathematics"}],"container-title":["Lecture Notes in Computer Science","Algorithms and Data Structures"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-40104-6_23","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,15]],"date-time":"2019-05-15T18:40:57Z","timestamp":1557945657000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-40104-6_23"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013]]},"ISBN":["9783642401039","9783642401046"],"references-count":19,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-40104-6_23","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2013]]}}}