{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,8]],"date-time":"2026-05-08T16:14:21Z","timestamp":1778256861083,"version":"3.51.4"},"reference-count":15,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[1987,12,1]],"date-time":"1987-12-01T00:00:00Z","timestamp":565315200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Combinatorica"],"published-print":{"date-parts":[[1987,12]]},"DOI":"10.1007\/bf02579324","type":"journal-article","created":{"date-parts":[[2007,3,22]],"date-time":"2007-03-22T22:20:05Z","timestamp":1174602005000},"page":"365-374","source":"Crossref","is-referenced-by-count":731,"title":["Randomized rounding: A technique for provably good algorithms and algorithmic proofs"],"prefix":"10.1007","volume":"7","author":[{"given":"Prabhakar","family":"Raghavan","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Clark D.","family":"Tompson","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"BF02579324_CR1","first-page":"476","volume-title":"Proceedings of the Seventeenth ACM Symposium on Theory of Computing","author":"R. Aharoni","year":"1985","unstructured":"R. Aharoni, P. Erd\u0151s andN. Linial, Dual Integer Linear Programs and the Relationship between their Optima,Proceedings of the Seventeenth ACM Symposium on Theory of Computing, ACM, New York, May1985, 476\u2013483."},{"key":"BF02579324_CR2","doi-asserted-by":"crossref","unstructured":"D. Angluin andL. G. Valiant, Fast probabilistic algorithms for Hamiltonian circuits and matchings,Journal of Computer and System Sciences,19, 155\u2013193.","DOI":"10.1016\/0022-0000(79)90045-X"},{"key":"BF02579324_CR3","doi-asserted-by":"crossref","first-page":"493","DOI":"10.1214\/aoms\/1177729330","volume":"23","author":"H. Chernoff","year":"1952","unstructured":"H. Chernoff, A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on the Sum of Observations,Annals of Math. Stat.,23 (1952), 493\u2013509.","journal-title":"Annals of Math. Stat."},{"key":"BF02579324_CR4","doi-asserted-by":"crossref","first-page":"691","DOI":"10.1137\/0205048","volume":"5","author":"S. Even","year":"1976","unstructured":"S. Even, A. Itai andA. Shamir, On the complexity of timetable and multi-commodity flow problems,SIAM Journal on Computing,5 (1976), 691\u2013703.","journal-title":"SIAM Journal on Computing"},{"key":"BF02579324_CR5","doi-asserted-by":"crossref","first-page":"155","DOI":"10.1007\/BF02579271","volume":"1","author":"Z. F\u00fcredi","year":"1981","unstructured":"Z. F\u00fcredi, Maximum degree and fractional matchings in uniform hypergraphs,Combinatorica 1 (1981), 155\u2013162.","journal-title":"Combinatorica"},{"key":"BF02579324_CR6","doi-asserted-by":"crossref","first-page":"713","DOI":"10.1214\/aoms\/1177728178","volume":"27","author":"W. Hoeffding","year":"1956","unstructured":"W. Hoeffding, On the distribution of the number of successes independent trials,Annals of Math. Stat.,27 (1956), 713\u2013721.","journal-title":"Annals of Math. Stat."},{"key":"BF02579324_CR7","doi-asserted-by":"crossref","first-page":"87","DOI":"10.1007\/BFb0121044","volume":"24","author":"T. C. Hu","year":"1985","unstructured":"T. C. Hu andM. T. Shing, A Decomposition Algorithm for Circuit Routing,Mathematical Programming Study,24 (1985), 87\u2013103.","journal-title":"Mathematical Programming Study"},{"key":"BF02579324_CR8","doi-asserted-by":"crossref","first-page":"373","DOI":"10.1007\/BF02579150","volume":"4","author":"N. Karmarkar","year":"1984","unstructured":"N. Karmarkar, A new polynomial-time algorithm for linear programming,Combinatorica 4 (1984), 373\u2013396.","journal-title":"Combinatorica"},{"key":"BF02579324_CR9","doi-asserted-by":"crossref","first-page":"85","DOI":"10.1007\/978-1-4684-2001-2_9","volume-title":"Complexity of Computer Computations","author":"R. M. Karp","year":"1972","unstructured":"R. M. Karp, Reducibility among combinatorial problems,Complexity of Computer Computations, (ed. R. N. Miller, J. W. Thatcher),Plenum Press, New York, (1972), 85\u2013104."},{"key":"BF02579324_CR10","doi-asserted-by":"crossref","unstructured":"R. M. Karp, F. T. Leighton, R. L. Rivest, C. D. Thompson, U. Vazirani andV. Vazirani Global Wire Routing in Two-Dimensional Arrays,Proc. 24th Annual Symp. on Foundations of Computer Science, (1983), 453\u2013459.","DOI":"10.1109\/SFCS.1983.23"},{"key":"BF02579324_CR11","doi-asserted-by":"crossref","first-page":"383","DOI":"10.1016\/0012-365X(75)90058-8","volume":"13","author":"L. Lov\u00e1sz","year":"1975","unstructured":"L. Lov\u00e1sz, On the ratio of optimal and fractional covers,Discrete Mathematics,13 (1975), 383\u2013390.","journal-title":"Discrete Mathematics"},{"key":"BF02579324_CR12","doi-asserted-by":"crossref","first-page":"277","DOI":"10.1016\/0020-0190(78)90016-9","volume":"7","author":"V. M. Malhotra","year":"1978","unstructured":"V. M. Malhotra, M. P. Kumar andS. N. Maheshwari, AnO(|V|3) algorithm for finding maximum flows in networks,Information Processing Letters,7 (1978), 277\u2013278.","journal-title":"Information Processing Letters"},{"key":"BF02579324_CR13","unstructured":"P. Raghavan andC. D. Thompson, Randomized Routing in Gate-Arrays,CSD\/84\/202, Computer Science Division, UC Berkeley, (1984)."},{"key":"BF02579324_CR14","unstructured":"P. Raghavan andC. D. Thompson, Provably Good Routing in Graphs: Regular Arrays,Proceedings of the Seventeenth ACM Symposium on Theory of Computing, ACM, New York, (1985), 79\u201387."},{"key":"BF02579324_CR15","unstructured":"P. Raghavan, Randomized Rouding and Discrete Ham-Sandwiches: Provably Good Algorithms for Routing and Packing Problems,PhD Thesis, Computer Science Division, UC Berkeley, (1986)."}],"container-title":["Combinatorica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF02579324.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF02579324\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF02579324","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,18]],"date-time":"2019-05-18T16:45:02Z","timestamp":1558197902000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF02579324"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1987,12]]},"references-count":15,"journal-issue":{"issue":"4","published-print":{"date-parts":[[1987,12]]}},"alternative-id":["BF02579324"],"URL":"https:\/\/doi.org\/10.1007\/bf02579324","relation":{},"ISSN":["0209-9683","1439-6912"],"issn-type":[{"value":"0209-9683","type":"print"},{"value":"1439-6912","type":"electronic"}],"subject":[],"published":{"date-parts":[[1987,12]]}}}