{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T15:57:23Z","timestamp":1725638243868},"publisher-location":"Berlin, Heidelberg","reference-count":17,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642255908"},{"type":"electronic","value":"9783642255915"}],"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-25591-5_2","type":"book-chapter","created":{"date-parts":[[2011,12,3]],"date-time":"2011-12-03T00:32:34Z","timestamp":1322872354000},"page":"6-9","source":"Crossref","is-referenced-by-count":0,"title":["Semidefinite Programming and Approximation Algorithms: A Survey"],"prefix":"10.1007","author":[{"given":"Sanjeev","family":"Arora","sequence":"first","affiliation":[]}],"member":"297","reference":[{"key":"2_CR1","doi-asserted-by":"crossref","unstructured":"Arora, S., Barak, B.: Computational Complexity: A Modern Approach. Cambridge University Press (2009)","DOI":"10.1017\/CBO9780511804090"},{"issue":"1","key":"2_CR2","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1090\/S0894-0347-07-00573-5","volume":"21","author":"S. Arora","year":"2008","unstructured":"Arora, S., Lee, J.R., Naor, A.: Euclidean distortion and the sparsest cut. J. Amer. Math. Soc.\u00a021(1), 1\u201321 (2008)","journal-title":"J. Amer. Math. Soc."},{"key":"2_CR3","unstructured":"Arora, S., Lund, C.: Hardness of approximations. In: Approximation Algorithms for NP-hard Problems. Course Technology (1996)"},{"key":"#cr-split#-2_CR4.1","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":"#cr-split#-2_CR4.2","unstructured":"Prelim version ACM STOC 2004"},{"key":"#cr-split#-2_CR5.1","doi-asserted-by":"crossref","unstructured":"Barak, B., Raghavendra, P., Steurer, D.: Rounding semidefinite programming hierarchies via global correlation. CoRR, abs\/1104.4680 (2011);","DOI":"10.1109\/FOCS.2011.95"},{"key":"#cr-split#-2_CR5.2","unstructured":"To appear in IEEE FOCS 2011"},{"key":"2_CR6","first-page":"102","volume-title":"SODA 2005: Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms","author":"S. Chawla","year":"2005","unstructured":"Chawla, S., Gupta, A., R\u00e4cke, H.: Embeddings of negative-type metrics and an improved approximation to generalized sparsest cut. In: SODA 2005: Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 102\u2013111. Society for Industrial and Applied Mathematics, Philadelphia (2005)"},{"key":"2_CR7","doi-asserted-by":"crossref","unstructured":"Goemans, M.X.: Semidefinite programming and combinatorial optimization. In: Proceedings of the International Congress of Mathematicians, Berlin, vol.\u00a0III, pp. 657\u2013666 (1998)","DOI":"10.4171\/dms\/1-3\/63"},{"issue":"6","key":"2_CR8","doi-asserted-by":"publisher","first-page":"1115","DOI":"10.1145\/227683.227684","volume":"42","author":"M.X. Goemans","year":"1995","unstructured":"Goemans, M.X., Williamson, D.P.: Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. J. Assoc. Comput. Mach.\u00a042(6), 1115\u20131145 (1995)","journal-title":"J. Assoc. Comput. Mach."},{"key":"2_CR9","unstructured":"Harsha, P., Charikar, M., Andrews, M., Arora, S., Khot, S., Moshkovitz, D., Zhang, L., Aazami, A., Desai, D., Gorodezky, I., Jagannathan, G., Kulikov, A.S., Mir, D.J., Newman, A., Nikolov, A., Pritchard, D., Spencer, G.: Limits of approximation algorithms: Pcps and unique games (dimacs tutorial lecture notes). CoRR, abs\/1002.3864 (2010)"},{"key":"2_CR10","doi-asserted-by":"crossref","unstructured":"Khot, S.: On the unique games conjecture (invited survey). In: Annual IEEE Conference on Computational Complexity, pp. 99\u2013121 (2010)","DOI":"10.1109\/CCC.2010.19"},{"key":"2_CR11","doi-asserted-by":"crossref","unstructured":"Raghavendra, P., Steurer, D.: Integrality gaps for strong SDP relaxations of Unique Games. In: FOCS, pp. 575\u2013585 (2009)","DOI":"10.1109\/FOCS.2009.73"},{"key":"2_CR12","doi-asserted-by":"crossref","unstructured":"Shmoys, D., Williamson, D.: Design of Approximation Algorithms. Cambridge University Press (2011)","DOI":"10.1017\/CBO9780511921735"},{"key":"2_CR13","unstructured":"Trevisan, L.: Inapproximability of combinatorial optimization problems. CoRR, cs.CC\/0409043 (2004)"},{"key":"2_CR14","unstructured":"Trevisan, L.: Inapproximability of combinatorial optimization problems. CoRR, cs.CC\/0409043 (2004)"},{"key":"2_CR15","volume-title":"Approximation Algorithms","author":"V. Vazirani","year":"2001","unstructured":"Vazirani, V.: Approximation Algorithms. Springer, Heidelberg (2001)"}],"container-title":["Lecture Notes in Computer Science","Algorithms and Computation"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-25591-5_2","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,6,11]],"date-time":"2023-06-11T11:15:28Z","timestamp":1686482128000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-25591-5_2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011]]},"ISBN":["9783642255908","9783642255915"],"references-count":17,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-25591-5_2","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2011]]}}}