{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,13]],"date-time":"2026-06-13T10:15:42Z","timestamp":1781345742700,"version":"3.54.1"},"publisher-location":"Berlin, Heidelberg","reference-count":42,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783642208065","type":"print"},{"value":"9783642208072","type":"electronic"}],"license":[{"start":{"date-parts":[[2011,1,1]],"date-time":"2011-01-01T00:00:00Z","timestamp":1293840000000},"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":[[2011]]},"DOI":"10.1007\/978-3-642-20807-2_24","type":"book-chapter","created":{"date-parts":[[2011,6,18]],"date-time":"2011-06-18T13:58:49Z","timestamp":1308405529000},"page":"301-314","source":"Crossref","is-referenced-by-count":27,"title":["Integrality Gaps of Linear and Semi-Definite Programming Relaxations for Knapsack"],"prefix":"10.1007","author":[{"given":"Anna R.","family":"Karlin","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Claire","family":"Mathieu","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"C. Thach","family":"Nguyen","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","reference":[{"key":"24_CR1","doi-asserted-by":"crossref","unstructured":"Alekhnovich, M., Arora, S., Tourlakis, I.: Towards strong non-approximability results in the Lov\u00e1sz-Schrijver hierarchy. In: ACM STOC (2005)","DOI":"10.1145\/1060590.1060634"},{"key":"24_CR2","doi-asserted-by":"publisher","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 of Computing\u00a02, 19\u201351 (2006)","journal-title":"Theory of Computing"},{"key":"24_CR3","doi-asserted-by":"crossref","unstructured":"Arora, S., Rao, S., Vazirani, U.V.: Expander flows, geometric embeddings and graph partitioning. J. ACM 56(2) (2009)","DOI":"10.1145\/1502793.1502794"},{"key":"24_CR4","unstructured":"Balas, E.: Facets of the Knapsack Polytope (1998)"},{"key":"24_CR5","doi-asserted-by":"publisher","first-page":"295","DOI":"10.1007\/BF01581273","volume":"58","author":"E. Balas","year":"1993","unstructured":"Balas, E., Ceria, S., Cornu\u00e9jols, G.: A lift-and-project cutting plane algorithm for mixed 0-1 programs. Mathematical Programming\u00a058, 295\u2013324 (1993)","journal-title":"Mathematical Programming"},{"key":"24_CR6","doi-asserted-by":"publisher","first-page":"119","DOI":"10.1137\/0134010","volume":"34","author":"E. Balas","year":"1978","unstructured":"Balas, E., Zemel, E.: Facets of the knapsack polytope from minimal covers. SIAM Journal on Applied Mathematics\u00a034, 119\u2013148 (1978)","journal-title":"SIAM Journal on Applied Mathematics"},{"key":"24_CR7","doi-asserted-by":"crossref","unstructured":"Bateni, M.H., Charikar, M., Guruswami, V.: MaxMin allocation via degree lower-bounded arborescences. In: ACM STOC (2009)","DOI":"10.1145\/1536414.1536488"},{"key":"24_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"299","DOI":"10.1007\/978-3-642-13036-6_23","volume-title":"Integer Programming and Combinatorial Optimization","author":"S. Benabbas","year":"2010","unstructured":"Benabbas, S., Magen, A.: Extending SDP integrality gaps to sherali-adams with applications to quadratic\u00a0programming and maxCutGain. In: Eisenbrand, F., Shepherd, F.B. (eds.) IPCO 2010. LNCS, vol.\u00a06080, pp. 299\u2013312. Springer, Heidelberg (2010)"},{"issue":"3","key":"24_CR9","doi-asserted-by":"publisher","first-page":"317","DOI":"10.1016\/j.orl.2007.09.003","volume":"36","author":"D. Bienstock","year":"2008","unstructured":"Bienstock, D.: Approximate formulations for 0-1 knapsack sets. Operational Research Letters\u00a036(3), 317\u2013320 (2008)","journal-title":"Operational Research Letters"},{"issue":"1","key":"24_CR10","doi-asserted-by":"publisher","first-page":"13","DOI":"10.1016\/j.disopt.2004.03.002","volume":"1","author":"D. Bienstock","year":"2004","unstructured":"Bienstock, D., Ozbay, N.: Tree-width and the Sherali-Adams operator. Discrete Optimization\u00a01(1), 13\u201321 (2004)","journal-title":"Discrete Optimization"},{"key":"24_CR11","doi-asserted-by":"crossref","unstructured":"Buresh-Oppenheim, J., Galesi, N., Hoory, S., Magen, A., Pitassi, T.: Rank bounds and integrality gaps for cutting plane procedures. In: IEEE FOCS (2003)","DOI":"10.1109\/SFCS.2003.1238206"},{"key":"24_CR12","unstructured":"Charikar, M.: On semidefinite programming relaxations for graph coloring and vertex cover. In: ACM-SIAM SODA (2002)"},{"key":"24_CR13","doi-asserted-by":"crossref","unstructured":"Charikar, M., Makarychev, K., Makarychev, Y.: Integrality gaps for Sherali-Adams relaxations. In: ACM STOC (2009)","DOI":"10.1145\/1536414.1536455"},{"key":"24_CR14","doi-asserted-by":"crossref","unstructured":"Cheeger, J., Kleiner, B., Naor, A.: A (logn)\u03a9 (1) integrality gap for the Sparsest Cut SDP. In: IEEE FOCS (2009)","DOI":"10.1109\/FOCS.2009.47"},{"key":"24_CR15","doi-asserted-by":"crossref","unstructured":"Chlamtac, E.: Approximation algorithms using hierarchies of semidefinite programming relaxations. In: IEEE FOCS (2007)","DOI":"10.1109\/FOCS.2007.72"},{"key":"24_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"49","DOI":"10.1007\/978-3-540-85363-3_5","volume-title":"Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques","author":"E. Chlamtac","year":"2008","unstructured":"Chlamtac, E., Singh, G.: Improved approximation guarantees through higher levels of SDP hierarchies. In: Goel, A., Jansen, K., Rolim, J.D.P., Rubinfeld, R. (eds.) APPROX and RANDOM 2008. LNCS, vol.\u00a05171, pp. 49\u201362. Springer, Heidelberg (2008)"},{"key":"24_CR17","unstructured":"Fernandez de la Vega, W., Kenyon-Mathieu, C.: Linear programming relaxations of MaxCut. In: ACM-SIAM SODA (2007)"},{"issue":"3","key":"24_CR18","doi-asserted-by":"publisher","first-page":"211","DOI":"10.1016\/S0167-6377(02)00221-3","volume":"31","author":"L.F. Escudero","year":"2003","unstructured":"Escudero, L.F., Garn, A.: An o(n log n) procedure for identifying facets of the knapsack polytope. Operational Research Letters\u00a031(3), 211\u2013218 (2003)","journal-title":"Operational Research Letters"},{"key":"24_CR19","doi-asserted-by":"crossref","unstructured":"Georgiou, K., Magen, A., Pitassi, T., Tourlakis, I.: Integrality gaps of 2\u2009\u2212\u2009o(1) for vertex cover SDPs in the Lov\u00e1sz-Schrijver hierarchy. In: IEEE FOCS (2007)","DOI":"10.1109\/FOCS.2007.35"},{"key":"24_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"140","DOI":"10.1007\/978-3-540-68891-4_10","volume-title":"Integer Programming and Combinatorial Optimization","author":"K. Georgiou","year":"2008","unstructured":"Georgiou, K., Magen, A., Tourlakis, I.: Vertex cover resists sDPs tightened by local hypermetric inequalities. In: Lodi, A., Panconesi, A., Rinaldi, G. (eds.) IPCO 2008. LNCS, vol.\u00a0IPCO, pp. 140\u2013153. Springer, Heidelberg (2008)"},{"key":"24_CR21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"125","DOI":"10.1007\/978-3-642-03685-9_10","volume-title":"Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques","author":"K. Georgiou","year":"2009","unstructured":"Georgiou, K., Magen, A., Tulsiani, M.: Optimal sherali-adams gaps from pairwise independence. In: Dinur, I., Jansen, K., Naor, J., Rolim, J. (eds.) APPROX 2009. LNCS, vol.\u00a05687, pp. 125\u2013139. Springer, Heidelberg (2009)"},{"key":"24_CR22","doi-asserted-by":"publisher","first-page":"113","DOI":"10.1016\/0166-218X(92)90162-4","volume":"39","author":"D. Hartvigsen","year":"1992","unstructured":"Hartvigsen, D., Zemel, E.: On the computational complexity of facets and valid inequalities for the knapsack problem. Discrete Applied Math.\u00a039, 113\u2013123 (1992)","journal-title":"Discrete Applied Math."},{"key":"24_CR23","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"164","DOI":"10.1007\/978-3-540-74208-1_12","volume-title":"Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques","author":"H. Hatami","year":"2007","unstructured":"Hatami, H., Magen, A., Markakis, E.: Integrality gaps of semidefinite programs for vertex cover and relations to \u21131 embeddability of negative type metrics. In: Charikar, M., Jansen, K., Reingold, O., Rolim, J.D.P. (eds.) RANDOM 2007 and APPROX 2007. LNCS, vol.\u00a04627, pp. 164\u2013179. Springer, Heidelberg (2007)"},{"key":"24_CR24","doi-asserted-by":"crossref","unstructured":"Ibarra, O.H., Kim, C.E.: Fast approximation algorithms for the knapsack and sum of subset problems. Journal of the ACM (1975)","DOI":"10.1145\/321906.321909"},{"key":"24_CR25","volume-title":"Knapsack problems","author":"H. Kellerer","year":"2003","unstructured":"Kellerer, H., Pferschy, U., Pisinger, D.: Knapsack problems. Springer, Heidelberg (2003)"},{"key":"24_CR26","doi-asserted-by":"crossref","unstructured":"Khot, S., Saket, R.: SDP integrality gaps with local \u21131-embeddability. In: IEEE FOCS (2009)","DOI":"10.1109\/FOCS.2009.37"},{"key":"24_CR27","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"293","DOI":"10.1007\/3-540-45535-3_23","volume-title":"Integer Programming and Combinatorial Optimization","author":"J.B. Lasserre","year":"2001","unstructured":"Lasserre, J.B.: An explicit exact SDP relaxation for nonlinear 0-1 programs. In: Aardal, K., Gerards, B. (eds.) IPCO 2001. LNCS, vol.\u00a02081, p. 293. Springer, Heidelberg (2001)"},{"key":"24_CR28","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, 796\u2013817 (2001)","journal-title":"SIAM Journal on Optimization"},{"key":"24_CR29","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, 470\u2013496 (2003)","journal-title":"Mathematics of Operations Research"},{"key":"24_CR30","unstructured":"Lawler, E.L.: Fast approximation algorithms for knapsack problems. In: IEEE FOCS (1997)"},{"key":"24_CR31","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 Journal on Optimization\u00a01, 166\u2013190 (1991)","journal-title":"SIAM Journal on Optimization"},{"key":"24_CR32","doi-asserted-by":"crossref","unstructured":"Pitassi, T., Segerlind, N.: Exponential lower bounds and integrality gaps for tree-like Lov\u00e1sz-Schrijver procedures. In: ACM-SIAM SODA (2009)","DOI":"10.1137\/1.9781611973068.40"},{"key":"24_CR33","doi-asserted-by":"crossref","unstructured":"Raghavendra, P.: Optimal algorithms and inapproximability results for every CSP? In: ACM STOC (2008)","DOI":"10.1145\/1374376.1374414"},{"key":"24_CR34","doi-asserted-by":"crossref","unstructured":"Raghavendra, P., Steurer, D.: Integrality gaps for strong SDP relaxations of unique games. In: IEEE FOCS (2009)","DOI":"10.1109\/FOCS.2009.73"},{"key":"24_CR35","doi-asserted-by":"crossref","unstructured":"Schoenebeck, G.: Linear level Lasserre lower bounds for certain k-csps. In: IEEE FOCS (2008)","DOI":"10.1109\/FOCS.2008.74"},{"key":"24_CR36","doi-asserted-by":"crossref","unstructured":"Schoenebeck, G., Trevisan, L., Tulsiani, M.: Tight integrality gaps for Lov\u00e1sz-Schrijver SDP relaxations of vertex cover and max cut. In: ACM STOC, pp. 302\u2013310 (2007)","DOI":"10.1145\/1250790.1250836"},{"key":"24_CR37","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, 411\u2013430 (1990)","journal-title":"SIAM Journal on Discrete Mathematics"},{"key":"24_CR38","unstructured":"Tourlakis, I.: New lower bounds for vertex cover in the Lov\u00e1sz-Schrijver hierarchy. In: IEEE CCC (2006)"},{"key":"24_CR39","doi-asserted-by":"crossref","unstructured":"Tulsiani, M.: CSP gaps and reductions in the Lasserre hierarchy. In: ACM STOC (2009)","DOI":"10.1145\/1536414.1536457"},{"key":"24_CR40","first-page":"49","volume":"77","author":"R. Weismantel","year":"1997","unstructured":"Weismantel, R.: On the 0\/1 knapsack polytope. Mathematical Programming\u00a077, 49\u201368 (1997)","journal-title":"Mathematical Programming"},{"issue":"2-3","key":"24_CR41","doi-asserted-by":"publisher","first-page":"251","DOI":"10.1016\/0166-218X(90)90148-6","volume":"29","author":"L.A. Wolsey","year":"1990","unstructured":"Wolsey, L.A.: Valid inequalities for 0-1 knapsacks and mips with generalised upper bound constraints. Discrete Applied Mathematics\u00a029(2-3), 251\u2013261 (1990)","journal-title":"Discrete Applied Mathematics"},{"key":"24_CR42","doi-asserted-by":"publisher","first-page":"760","DOI":"10.1287\/moor.14.4.760","volume":"14","author":"E. Zemel","year":"1989","unstructured":"Zemel, E.: Easily computable facets of the knapsack problem. Mathematics of Operations Research\u00a014, 760\u2013774 (1989)","journal-title":"Mathematics of Operations Research"}],"container-title":["Lecture Notes in Computer Science","Integer Programming and Combinatoral Optimization"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-20807-2_24","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,6,12]],"date-time":"2019-06-12T00:16:02Z","timestamp":1560298562000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-20807-2_24"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011]]},"ISBN":["9783642208065","9783642208072"],"references-count":42,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-20807-2_24","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2011]]}}}