{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,18]],"date-time":"2025-11-18T12:11:16Z","timestamp":1763467876644},"publisher-location":"Berlin, Heidelberg","reference-count":29,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540853626"},{"type":"electronic","value":"9783540853633"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/978-3-540-85363-3_5","type":"book-chapter","created":{"date-parts":[[2008,8,27]],"date-time":"2008-08-27T19:29:28Z","timestamp":1219865368000},"page":"49-62","source":"Crossref","is-referenced-by-count":18,"title":["Improved Approximation Guarantees through Higher Levels of SDP Hierarchies"],"prefix":"10.1007","author":[{"given":"Eden","family":"Chlamtac","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Gyanit","family":"Singh","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"5_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 37th Annual ACM Symposium on Theory of Computing, pp. 294\u2013303 (2005)","DOI":"10.1145\/1060590.1060634"},{"key":"5_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":"5_CR3","doi-asserted-by":"crossref","unstructured":"Arora, S., Chlamtac, E., Charikar, M.: New approximation guarantee for chromatic number. In: Proceedings of 38th ACM Symposium of Theory of Computing, pp. 215\u2013224 (2006)","DOI":"10.1145\/1132516.1132548"},{"key":"5_CR4","doi-asserted-by":"crossref","unstructured":"Arora, S., Rao, S., Vazirani, U.: Expander flows, geometric embeddings and graph partitioning. In: Proceedings of the 36th Annual ACM Symposium on Theory of Computing, pp. 222\u2013231 (2004)","DOI":"10.1145\/1007352.1007355"},{"key":"5_CR5","unstructured":"Charikar, M., Makarychev, K., Makarychev, Y.: Integrality Gaps for Sherali-Adams Relaxations (manuscript)"},{"key":"5_CR6","doi-asserted-by":"crossref","unstructured":"Charikar, M., Makarychev, K., Makarychev, Y.: Near-Optimal Algorithms for Unique Games. In: Proceedings of the 38th Annual ACM Symposium on Theory of Computing, pp. 205\u2013214 (2006)","DOI":"10.1145\/1132516.1132547"},{"key":"5_CR7","doi-asserted-by":"crossref","unstructured":"Chlamtac, E.: Approximation Algorithms Using Hierarchies of Semidefinite Programming Relaxations. In: Proceedings of 48th IEEE Symposium on Foundations of Computer Science, pp. 691\u2013701 (2007)","DOI":"10.1109\/FOCS.2007.72"},{"issue":"2-3","key":"5_CR8","doi-asserted-by":"publisher","first-page":"210","DOI":"10.1016\/j.tcs.2006.05.011","volume":"361","author":"E.D. Klerk","year":"2006","unstructured":"Klerk, E.D., Laurent, M., Parrilo, P.: A PTAS for the minimization of polynomials of fixed degree over the simplex. Theoretical Computer Science\u00a0361(2-3), 210\u2013225 (2006)","journal-title":"Theoretical Computer Science"},{"issue":"2","key":"5_CR9","doi-asserted-by":"publisher","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 Journal on Computing\u00a032(2), 345\u2013370 (2003)","journal-title":"SIAM Journal on Computing"},{"key":"5_CR10","volume-title":"An Introduction to Probability Theory and Its Applications","author":"W. Feller","year":"1968","unstructured":"Feller, W.: An Introduction to Probability Theory and Its Applications, 3rd edn., vol.\u00a01. John Wiley & Sons, Chichester (1968)","edition":"3"},{"key":"5_CR11","doi-asserted-by":"crossref","unstructured":"Georgiou, K., Magen, A., Pitassi, T., Tourlakis, I.: Integrality gaps of 2\u2013o(1) for vertex cover in the Lov\u00e1sz-Schrijver hierarchy. In: Proceedings of 48th IEEE Symposium on Foundations of Computer Science, pp. 702\u2013712 (2007)","DOI":"10.1109\/FOCS.2007.35"},{"issue":"6","key":"5_CR12","doi-asserted-by":"publisher","first-page":"1115","DOI":"10.1145\/227683.227684","volume":"42","author":"M. Goemans","year":"1995","unstructured":"Goemans, M., Williamson, D.: Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. Journal of the ACM\u00a042(6), 1115\u20131145 (1995)","journal-title":"Journal of the ACM"},{"issue":"4","key":"5_CR13","doi-asserted-by":"publisher","first-page":"798","DOI":"10.1145\/502090.502098","volume":"48","author":"J. H\u00e5stad","year":"2001","unstructured":"H\u00e5stad, J.: Some optimal inapproximability results. Journal of the ACM\u00a048(4), 798\u2013859 (2001)","journal-title":"Journal of the ACM"},{"issue":"1","key":"5_CR14","doi-asserted-by":"publisher","first-page":"72","DOI":"10.1016\/S0196-6774(02)00217-1","volume":"45","author":"E. Halperin","year":"2002","unstructured":"Halperin, E., Nathaniel, R., Zwick, U.: Coloring k-colorable graphs using relatively small palettes. J. Algorithms\u00a045(1), 72\u201390 (2002)","journal-title":"J. Algorithms"},{"issue":"2","key":"5_CR15","doi-asserted-by":"publisher","first-page":"246","DOI":"10.1145\/274787.274791","volume":"45","author":"D. Karger","year":"1998","unstructured":"Karger, D., Motwani, R., Sudan, M.: Approximate graph coloring by semidefinite programming. Journal of the ACM\u00a045(2), 246\u2013265 (1998)","journal-title":"Journal of the ACM"},{"key":"5_CR16","doi-asserted-by":"crossref","unstructured":"Karloff, H., Zwick, U.: A 7\/8-approximation algorithm for max 3SAT? In: Proceedings of 38th IEEE Symposium on Foundations of Computer Science, pp. 406\u2013415 (1997)","DOI":"10.1109\/SFCS.1997.646129"},{"key":"5_CR17","doi-asserted-by":"crossref","unstructured":"Khot, S.: On the power of unique 2-prover 1-round games. In: Proceedings of the 34th ACM Symposium on Theory of Computing, pp. 767\u2013775 (2002)","DOI":"10.1145\/510014.510017"},{"issue":"1","key":"5_CR18","doi-asserted-by":"publisher","first-page":"319","DOI":"10.1137\/S0097539705447372","volume":"37","author":"S. Khot","year":"2007","unstructured":"Khot, S., Kindler, G., Mossel, E., O\u2019Donnell, R.: Optimal inapproximability results for MAX-CUT and other 2-variable CSPs? SIAM Journal on Computing\u00a037(1), 319\u2013357 (2007); ECCC Report TR05-101 (2005)","journal-title":"SIAM Journal on Computing"},{"issue":"1","key":"5_CR19","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1006\/jagm.2001.1173","volume":"41","author":"M. Krivelevich","year":"2001","unstructured":"Krivelevich, M., Nathaniel, R., Sudakov, B.: Approximating coloring and maximum independent sets in 3-uniform hypergraphs. Journal of Algorithms\u00a041(1), 99\u2013113 (2001)","journal-title":"Journal of Algorithms"},{"issue":"3","key":"5_CR20","doi-asserted-by":"publisher","first-page":"460","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), 460\u2013496 (2003)","journal-title":"Mathematics of Operations Research"},{"key":"5_CR21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","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, pp. 293\u2013303. Springer, Heidelberg (2001)"},{"issue":"2","key":"5_CR22","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-functioins and 0-1 optimization. SIAM Journal on Optimization\u00a01(2), 166\u2013190 (1991)","journal-title":"SIAM Journal on Optimization"},{"issue":"1","key":"5_CR23","doi-asserted-by":"publisher","first-page":"135","DOI":"10.1016\/j.jco.2006.07.002","volume":"23","author":"J. Nie","year":"2007","unstructured":"Nie, J., Schweighofer, M.: On the complexity of Putinar\u2019s Positivstellensatz. Journal of Complexity\u00a023(1), 135\u2013150 (2007)","journal-title":"Journal of Complexity"},{"key":"5_CR24","doi-asserted-by":"crossref","unstructured":"Raghavendra, P.: Optimal Algorithms and Inapproximability Results For Every CSP? In: Proceedings of 30th ACM Symposium on Theory of Computing, pp. 245\u2013254 (2008)","DOI":"10.1145\/1374376.1374414"},{"key":"5_CR25","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 29th ACM Symposium on Theory of Computing, pp. 302\u2013310 (2007)","DOI":"10.1145\/1250790.1250836"},{"issue":"3","key":"5_CR26","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"},{"key":"5_CR27","unstructured":"Schoenebeck, G.: Personal communication"},{"key":"5_CR28","unstructured":"de la Vega, F.W., Kenyon-Mathieu, C.: Linear programming relaxations of maxcut. In: Proceedings of 18th ACM Symposium on Discrete Algorithms, pp. 53\u201361 (2007)"},{"key":"5_CR29","unstructured":"Zwick, U.: Computer assisted proof of optimal approximability results. In: Proceedings of 13th ACM Symposium on Discrete Algorithms, pp. 496\u2013505 (2002)"}],"container-title":["Lecture Notes in Computer Science","Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-85363-3_5.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,24]],"date-time":"2020-11-24T02:24:23Z","timestamp":1606184663000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-85363-3_5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["9783540853626","9783540853633"],"references-count":29,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-85363-3_5","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[]}}