{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,11,11]],"date-time":"2026-11-11T00:34:14Z","timestamp":1794357254348,"version":"4.9.0"},"publisher-location":"Boston, MA","reference-count":16,"publisher":"Springer US","isbn-type":[{"value":"9780387307701","type":"print"},{"value":"9780387301624","type":"electronic"}],"license":[{"start":{"date-parts":[[2008,1,1]],"date-time":"2008-01-01T00:00:00Z","timestamp":1199145600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2008,1,1]],"date-time":"2008-01-01T00:00:00Z","timestamp":1199145600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2008]]},"DOI":"10.1007\/978-0-387-30162-4_327","type":"book-chapter","created":{"date-parts":[[2008,6,26]],"date-time":"2008-06-26T14:29:45Z","timestamp":1214490585000},"page":"737-740","source":"Crossref","is-referenced-by-count":2,"title":["Randomized Rounding"],"prefix":"10.1007","author":[{"given":"Rajmohan","family":"Rajaraman","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","reference":[{"key":"327_CR1_327","volume-title":"The Probabilistic Method","author":"N. Alon","year":"1991","unstructured":"Alon, N., Spencer, J.H.: The Probabilistic Method. Wiley, New York (1991)"},{"key":"327_CR2_327","doi-asserted-by":"publisher","first-page":"284","DOI":"10.1145\/1060590.1060633","volume-title":"STOC '05: Proceedings of the thirty-seventh annual ACM symposium on Theory of computing","author":"M. Andrews","year":"2005","unstructured":"Andrews, M., Zhang, L.: Hardness of the undirected congestion minimization problem. In: STOC '05: Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, pp.\u00a0284\u2013293. ACM Press, New York (2005)"},{"key":"327_CR3_327","doi-asserted-by":"crossref","unstructured":"Arora, S., Rao, S., Vazirani, U.V.: Expander flows, geometric embeddings and graph partitioning. In: STOC, pp.\u00a0222\u2013231. (2004)","DOI":"10.1145\/1007352.1007355"},{"issue":"3","key":"327_CR4_327","doi-asserted-by":"publisher","first-page":"564","DOI":"10.1006\/jcss.1999.1687","volume":"60","author":"G. Calinescu","year":"2000","unstructured":"Calinescu, G., Karloff, H.J., Rabani, Y.: An improved approximation algorithm for multiway cut. J.\u00a0Comput. Syst. Sci. 60(3), 564\u2013574 (2000)","journal-title":"J. Comput. Syst. Sci."},{"key":"327_CR5_327","doi-asserted-by":"publisher","first-page":"493","DOI":"10.1214\/aoms\/1177729330","volume":"23","author":"H. Chernoff","year":"1952","unstructured":"Chernoff, H.: A\u00a0measure of the asymptotic efficiency for tests of a\u00a0hypothesis based on the sum of observations. Ann. Math. Stat. 23, 493\u2013509 (1952)","journal-title":"Ann. Math. Stat."},{"key":"327_CR6_327","doi-asserted-by":"publisher","first-page":"165","DOI":"10.1145\/1250790.1250816","volume-title":"STOC '07: Proceedings of the thirty-ninth annual ACM symposium on Theory of computing","author":"J. Chuzhoy","year":"2007","unstructured":"Chuzhoy, J., Guruswami, V., Khanna, S., Talwar, K.: Hardness of routing with congestion in directed graphs. In: STOC '07: Proceedings of the thirty-ninth annual ACM symposium on Theory of computing, pp.\u00a0165\u2013178. ACM Press, New York (2007)"},{"key":"327_CR7_327","doi-asserted-by":"publisher","first-page":"656","DOI":"10.1137\/S0895480192243516","volume":"7","author":"M.X. Goemans","year":"1994","unstructured":"Goemans, M.X., Williamson, D.P.: New 3\/4-approximation algorithms for the maximum satisfiability problem. SIAM J.\u00a0Discret. Math. 7, 656\u2013666 (1994)","journal-title":"SIAM J. Discret. Math."},{"issue":"6","key":"327_CR8_327","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.\u00a0ACM 42(6), 1115\u20131145 (1995)","journal-title":"J. ACM"},{"key":"327_CR9_327","doi-asserted-by":"publisher","first-page":"473","DOI":"10.1016\/S0022-0000(03)00066-7","volume":"67","author":"V. Guruswami","year":"2003","unstructured":"Guruswami, V., Khanna, S., Rajaraman, R., Shepherd, B., Yannakakis, M.: Near-optimal hardness results and approximation algorithms for edge-disjoint paths and related problems. J.\u00a0Comput. Syst. Sci. 67, 473\u2013496 (2003)","journal-title":"J. Comput. Syst. Sci."},{"issue":"3","key":"327_CR10_327","doi-asserted-by":"publisher","first-page":"555","DOI":"10.1137\/0211045","volume":"11","author":"D.S. Hochbaum","year":"1982","unstructured":"Hochbaum, D.S.: Approximation algorithms for the set covering and vertex cover problems. SIAM J.\u00a0Comput. 11(3), 555\u2013556 (1982)","journal-title":"SIAM J. Comput."},{"key":"327_CR11_327","doi-asserted-by":"publisher","first-page":"713","DOI":"10.1214\/aoms\/1177728178","volume":"27","author":"W. Hoeffding","year":"1956","unstructured":"Hoeffding, W.: On the distribution of the number of successes in independent trials. Ann. Math. Stat. 27, 713\u2013721 (1956)","journal-title":"Ann. Math. Stat."},{"key":"327_CR12_327","doi-asserted-by":"publisher","first-page":"373","DOI":"10.1007\/BF02579150","volume":"4","author":"N. Karmarkar","year":"1984","unstructured":"Karmarkar, N.: A\u00a0new polynomial-time algorithm for linear programming. Combinatorica 4, 373\u2013395 (1984)","journal-title":"Combinatorica"},{"key":"327_CR13_327","first-page":"191","volume":"20","author":"L.G. Khachiyan","year":"1979","unstructured":"Khachiyan, L.G.: A\u00a0polynomial algorithm for linear programming. Soviet Math. Doklady 20, 191\u2013194 (1979)","journal-title":"Soviet Math. Doklady"},{"key":"327_CR14_327","doi-asserted-by":"publisher","first-page":"365","DOI":"10.1007\/BF02579324","volume":"7","author":"P. Raghavan","year":"1987","unstructured":"Raghavan, P., Thompson, C.: Randomized rounding: A technique for provably good algorithms and algorithmic proofs. Combinatorica 7 (1987)","journal-title":"Combinatorica"},{"key":"327_CR15_327","doi-asserted-by":"crossref","unstructured":"Srinivasan, A.: Improved approximations of packing and covering problems. In: Proceedings of the 27th Annual ACM Symposium on Theory of Computing, pp.\u00a0268\u2013276 (1995)","DOI":"10.1145\/225058.225138"},{"key":"327_CR16_327","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-04565-7","volume-title":"Approximation Algorithms","author":"V.V. Vazirani","year":"2003","unstructured":"Vazirani, V.: Approximation Algorithms. Springer (2003)"}],"container-title":["Encyclopedia of Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-0-387-30162-4_327","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,9,2]],"date-time":"2022-09-02T23:30:39Z","timestamp":1662161439000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-0-387-30162-4_327"}},"subtitle":["1987; Raghavan, Thompson"],"short-title":[],"issued":{"date-parts":[[2008]]},"ISBN":["9780387307701","9780387301624"],"references-count":16,"URL":"https:\/\/doi.org\/10.1007\/978-0-387-30162-4_327","relation":{"is-part-of":[{"id-type":"doi","id":"https:\/\/doi.org\/10.1007\/978-0-387-30162-4","asserted-by":"object"}]},"subject":[],"published":{"date-parts":[[2008]]}}}