{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T23:46:01Z","timestamp":1725493561168},"publisher-location":"Berlin, Heidelberg","reference-count":16,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540422877"},{"type":"electronic","value":"9783540482246"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2001]]},"DOI":"10.1007\/3-540-48224-5_18","type":"book-chapter","created":{"date-parts":[[2007,10,28]],"date-time":"2007-10-28T02:29:04Z","timestamp":1193538544000},"page":"213-224","source":"Crossref","is-referenced-by-count":15,"title":["The RPR 2 Rounding Technique for Semidefinite Programs"],"prefix":"10.1007","author":[{"given":"Uriel","family":"Feige","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Michael","family":"Langberg","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2001,7,4]]},"reference":[{"key":"18_CR1","doi-asserted-by":"crossref","unstructured":"U. Feige and M.X. Goemans. Approximating the value of two prover proof systems with applications to Max-2-Sat and Max-Dicut. Proc. of the 3rd Israel Symposium on Theory of Computing and Systems, pages 182\u2013189, 1995.","DOI":"10.1109\/ISTCS.1995.377033"},{"key":"18_CR2","doi-asserted-by":"publisher","first-page":"67","DOI":"10.1007\/BF02523688","volume":"18","author":"A. Frieze","year":"1997","unstructured":"A. Frieze and M. Jerrum. Improved approximation algorithms for Max-k-Cut and Max-Bisection. Algorithmica, 18:67\u201381, 1997.","journal-title":"Algorithmica"},{"key":"18_CR3","unstructured":"U. Feige, M. Karpinski, and M. Langberg. Improved approximation of Max-Cut on graphs of bounded degree. ECCC, TR00-021, 2000."},{"key":"18_CR4","doi-asserted-by":"crossref","unstructured":"U. Feige and M. Langberg. The RPR 2 rounding technique for semidefinite programs. Manuscript, http:\/\/www.wisdom.weizmann.ac.il\/~mikel , 2001.","DOI":"10.1007\/3-540-48224-5_18"},{"key":"18_CR5","doi-asserted-by":"crossref","unstructured":"U. Feige and G. Schechtman. On the optimality of the random hyperplane rounding technique for MAX CUT. Manuscript, 2001.","DOI":"10.1002\/rsa.10036"},{"issue":"4","key":"18_CR6","doi-asserted-by":"publisher","first-page":"656","DOI":"10.1137\/S0895480192243516","volume":"7","author":"M.X. Goemans","year":"1994","unstructured":"M.X. Goemans and D.P. Williamson. New 3\/4-approximation algorithms for the maximum satisfiability problem. SIAM Journal on Discrete Mathematics, 7(4):656\u2013666, 1994.","journal-title":"SIAM Journal on Discrete Mathematics"},{"key":"18_CR7","doi-asserted-by":"publisher","first-page":"1115","DOI":"10.1145\/227683.227684","volume":"42","author":"M.X. Goemans","year":"1995","unstructured":"M.X. Goemans and D.P. Williamson. Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. Journal of ACM, 42:1115\u20131145, 1995.","journal-title":"Journal of ACM"},{"issue":"3","key":"18_CR8","doi-asserted-by":"publisher","first-page":"555","DOI":"10.1137\/0211045","volume":"11","author":"D.S. Hochbaum","year":"1982","unstructured":"D.S. Hochbaum. Approximation algorithms for the set covering and vertex cover problem. SIAM J. of Computing, 11(3):555\u2013556, 1982.","journal-title":"SIAM J. of Computing"},{"key":"18_CR9","doi-asserted-by":"crossref","unstructured":"E. Halperin and U. Zwick. Improved approximation algorithms for maximum graph bisection problems. Manuscript, 2000.","DOI":"10.1007\/3-540-45535-3_17"},{"issue":"2","key":"18_CR10","doi-asserted-by":"publisher","first-page":"246","DOI":"10.1145\/274787.274791","volume":"45","author":"D. Karger","year":"1998","unstructured":"D. Karger, R. Motwani, and M. Sudan. Approximate graph coloring by semidefinite programming. Journal of ACM, 45(2):246\u2013265, 1998.","journal-title":"Journal of ACM"},{"key":"18_CR11","doi-asserted-by":"crossref","unstructured":"H. Karloff and U. Zwick. A 7\/8-approximation algorithm for Max-3-Sat? In Proceedings of the 38th Annual IEEE Symposium on Foundations of Computer Science, pages 406\u2013415, 1997.","DOI":"10.1109\/SFCS.1997.646129"},{"key":"18_CR12","doi-asserted-by":"publisher","first-page":"141","DOI":"10.1080\/10556789808805690","volume":"9","author":"Y. E. Nesterov","year":"1998","unstructured":"Y. E. Nesterov. Semidefinite relaxation and nonconvex quadratic optimization. Optimization Methods and Software, 9:141\u2013160, 1998.","journal-title":"Optimization Methods and Software"},{"key":"18_CR13","volume-title":"Probability theory","author":"A. Renyi","year":"1970","unstructured":"A. Renyi. Probability theory. Elsevier, New York, 1970."},{"issue":"7","key":"18_CR14","doi-asserted-by":"publisher","first-page":"365","DOI":"10.1007\/BF02579324","volume":"7","author":"P. Raghavan","year":"1987","unstructured":"P. Raghavan and C.D. Thompson. Randomized rounding: A technique for provably good algorithms and algorithmic proofs. Combinatorica, 7(7):365\u2013374, 1987.","journal-title":"Combinatorica"},{"key":"18_CR15","unstructured":"Y. Ye. A 0.699-approximation algorithm for Max-Bisection. Manuscript, available at URL http:\/\/dollar.biz.uiowa.edu\/col\/ye\/ , 1999."},{"key":"18_CR16","doi-asserted-by":"crossref","unstructured":"U. Zwick. Outward rotations: a new tool for rounding solutions of semidefinite programming relaxations, with application to Max-Cut and other problems. In Proceedings of the 31th ACM Symposium on Theory of Computing, pages 679\u2013687, 1999.","DOI":"10.1145\/301250.301431"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-48224-5_18","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,3]],"date-time":"2019-05-03T22:28:41Z","timestamp":1556922521000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-48224-5_18"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2001]]},"ISBN":["9783540422877","9783540482246"],"references-count":16,"URL":"https:\/\/doi.org\/10.1007\/3-540-48224-5_18","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2001]]}}}