{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T06:30:18Z","timestamp":1787293818432,"version":"build-2736575974"},"reference-count":37,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2006,5,1]],"date-time":"2006-05-01T00:00:00Z","timestamp":1146441600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2006,5]]},"abstract":"<jats:p>We develop a new randomized rounding approach for fractional vectors defined on the edge-sets of bipartite graphs. We show various ways of combining this technique with other ideas, leading to improved (approximation) algorithms for various problems. These include:---low congestion multi-path routing;---richer random-graph models for graphs with a given degree-sequence;---improved approximation algorithms for: (i) throughput-maximization in broadcast scheduling, (ii) delay-minimization in broadcast scheduling, as well as (iii) capacitated vertex cover; and---fair scheduling of jobs on unrelated parallel machines.<\/jats:p>","DOI":"10.1145\/1147954.1147956","type":"journal-article","created":{"date-parts":[[2006,10,18]],"date-time":"2006-10-18T14:11:32Z","timestamp":1161180692000},"page":"324-360","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":189,"title":["Dependent rounding and its applications to approximation algorithms"],"prefix":"10.1145","volume":"53","author":[{"given":"Rajiv","family":"Gandhi","sequence":"first","affiliation":[{"name":"Rutgers University, Camden, New Jersey"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Samir","family":"Khuller","sequence":"additional","affiliation":[{"name":"University of Maryland, College Park, Maryland"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Srinivasan","family":"Parthasarathy","sequence":"additional","affiliation":[{"name":"University of Maryland, College Park, Maryland"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Aravind","family":"Srinivasan","sequence":"additional","affiliation":[{"name":"University of Maryland, College Park, Maryland"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2006,5]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1023\/B:JOCO.0000038913.96607.c2"},{"key":"e_1_2_1_2_1","volume-title":"SODA '05: Proceedings of the 16th annual ACM-SIAM Symposium on Discrete Algorithms. Society for Industrial and Applied Mathematics","author":"Bansal N.","unstructured":"Bansal , N. , Charikar , M. , Khanna , S. , and Naor , J. S . 2005. Approximating the average response time in broadcast scheduling . In SODA '05: Proceedings of the 16th annual ACM-SIAM Symposium on Discrete Algorithms. Society for Industrial and Applied Mathematics , Philadelphia, PA, 215--221.]] Bansal, N., Charikar, M., Khanna, S., and Naor, J. S. 2005. Approximating the average response time in broadcast scheduling. In SODA '05: Proceedings of the 16th annual ACM-SIAM Symposium on Discrete Algorithms. Society for Industrial and Applied Mathematics, Philadelphia, PA, 215--221.]]"},{"key":"e_1_2_1_3_1","unstructured":"Bansal N. Coppersmith D. and Sviridenko M. 2004. Improved approximation algorithms for broadcast scheduling. IBM Tech Report RC23468.]]  Bansal N. Coppersmith D. and Sviridenko M. 2004. Improved approximation algorithms for broadcast scheduling. IBM Tech Report RC23468.]]"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/502102.502107"},{"key":"e_1_2_1_5_1","volume-title":"Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms., ACM","author":"Bar-Noy A.","unstructured":"Bar-Noy , A. , Guha , S. , Katz , Y. , Naor , J. , Schieber , B. , and Shachnai , H . 2002. Throughput maximization of real-time scheduling with batching . In Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms., ACM , New York, 742--751.]] Bar-Noy, A., Guha, S., Katz, Y., Naor, J., Schieber, B., and Shachnai, H. 2002. Throughput maximization of real-time scheduling with batching. In Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms., ACM, New York, 742--751.]]"},{"key":"e_1_2_1_6_1","volume-title":"Proceedings of the 11th Annual ACM-SIAM Symposium on Discrete Algorithms., ACM","author":"Bartal Y.","unstructured":"Bartal , Y. , and Muthukrishnan , S . 2000. Minimizing maximum response time in scheduling broadcasts . In Proceedings of the 11th Annual ACM-SIAM Symposium on Discrete Algorithms., ACM , New York, 558--559.]] Bartal, Y., and Muthukrishnan, S. 2000. Minimizing maximum response time in scheduling broadcasts. In Proceedings of the 11th Annual ACM-SIAM Symposium on Discrete Algorithms., ACM, New York, 558--559.]]"},{"key":"e_1_2_1_7_1","volume-title":"Proceedings of the annual ACM-SIAM Symposium on Discrete Algorithms., ACM","author":"Chekuri C.","unstructured":"Chekuri , C. , and Khanna , S . 2000. A PTAS for the multiple knapsack problem . In Proceedings of the annual ACM-SIAM Symposium on Discrete Algorithms., ACM , New York, 213--222.]] Chekuri, C., and Khanna, S. 2000. A PTAS for the multiple knapsack problem. In Proceedings of the annual ACM-SIAM Symposium on Discrete Algorithms., ACM, New York, 213--222.]]"},{"key":"e_1_2_1_8_1","volume-title":"Proceedings of the IEEE Symposium on Foundations of Computer Science., IEEE Computer Society Press","author":"Chuzhoy J.","unstructured":"Chuzhoy , J. , and Naor , J . 2002. Covering problems with hard capacities . In Proceedings of the IEEE Symposium on Foundations of Computer Science., IEEE Computer Society Press , Los Alamitos, CA, 481--489.]] Chuzhoy, J., and Naor, J. 2002. Covering problems with hard capacities. In Proceedings of the IEEE Symposium on Foundations of Computer Science., IEEE Computer Society Press, Los Alamitos, CA, 481--489.]]"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1080\/15427951.2004.10129078"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.10084"},{"key":"e_1_2_1_11_1","volume-title":"Spider: A simple and flexible tool for design and provisioning of protected lightpaths in optical networks. Bell Labs Tech. J. 6.]]","author":"Davis R. D.","year":"2001","unstructured":"Davis , R. D. , Kumaran , K. , Liu , G. , and Saniee , I . 2001 . Spider: A simple and flexible tool for design and provisioning of protected lightpaths in optical networks. Bell Labs Tech. J. 6.]] Davis, R. D., Kumaran, K., Liu, G., and Saniee, I. 2001. Spider: A simple and flexible tool for design and provisioning of protected lightpaths in optical networks. Bell Labs Tech. J. 6.]]"},{"key":"e_1_2_1_12_1","volume-title":"Proceedings of the ACM-SIAM Symposium on Discrete Algorithms., ACM","author":"Doerr B.","year":"2003","unstructured":"Doerr , B. 2003 . Non-independent randomized rounding . In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms., ACM , New York, 506--507.]] Doerr, B. 2003. Non-independent randomized rounding. In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms., ACM, New York, 506--507.]]"},{"key":"e_1_2_1_13_1","doi-asserted-by":"crossref","unstructured":"Doshi B. T. Dravida S. Harshavardhana P. Hauser O. and Wang Y. 1999. Optical network design and restoration. Bell Labs Tech. J. Issue on Optical Networking 4.]]  Doshi B. T. Dravida S. Harshavardhana P. Hauser O. and Wang Y. 1999. Optical network design and restoration. Bell Labs Tech. J. Issue on Optical Networking 4.]]","DOI":"10.1002\/bltj.2147"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1023\/B:JOSH.0000019682.75022.96"},{"key":"e_1_2_1_15_1","volume-title":"Proceedings of the ACM-SIAM Symposium on Discrete Algorithms., ACM","author":"Eubank S.","unstructured":"Eubank , S. , Kumar , V. S. A. , Marathe , M. V. , Srinivasan , A. , and Wang , N . 2004. Structural and algorithmic aspects of massive social networks . In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms., ACM , New York, 711--720.]] Eubank, S., Kumar, V. S. A., Marathe, M. V., Srinivasan, A., and Wang, N. 2004. Structural and algorithmic aspects of massive social networks. In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms., ACM, New York, 711--720.]]"},{"key":"e_1_2_1_16_1","volume-title":"Graph Algorithms","author":"Even S.","unstructured":"Even , S. 1979. Graph Algorithms . Computer Science Press .]] Even, S. 1979. Graph Algorithms. Computer Science Press.]]"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/316188.316229"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/s101070100271"},{"key":"e_1_2_1_19_1","unstructured":"Gailis R. and Khuller S. Broadcast scheduling with deadlines. http:\/\/www.cs.umd.edu\/users\/samir\/grant\/renars.ps.]]  Gailis R. and Khuller S. Broadcast scheduling with deadlines. http:\/\/www.cs.umd.edu\/users\/samir\/grant\/renars.ps.]]"},{"key":"e_1_2_1_20_1","volume-title":"Proceedings of the International Colloquium on Automata, Languages, and Programming. 164--175","author":"Gandhi R.","unstructured":"Gandhi , R. , Halperin , E. , Khuller , S. , Kortsarz , G. , and Srinivasan , A . 2003. An improved approximation algorithm for vertex cover with hard capacities . In Proceedings of the International Colloquium on Automata, Languages, and Programming. 164--175 .]] Gandhi, R., Halperin, E., Khuller, S., Kortsarz, G., and Srinivasan, A. 2003. An improved approximation algorithm for vertex cover with hard capacities. In Proceedings of the International Colloquium on Automata, Languages, and Programming. 164--175.]]"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-003-1058-x"},{"key":"e_1_2_1_22_1","volume-title":"Proceedings of the IEEE Symposium on Foundations of Computer Science., IEEE Computer Science Press","author":"Gandhi R.","unstructured":"Gandhi , R. , Khuller , S. , Parthasarathy , S. , and Srinivasan , A . 2002. Dependent rounding in bipartite graphs . In Proceedings of the IEEE Symposium on Foundations of Computer Science., IEEE Computer Science Press , Los Alamitos, CA, 323--332.]] Gandhi, R., Khuller, S., Parthasarathy, S., and Srinivasan, A. 2002. Dependent rounding in bipartite graphs. In Proceedings of the IEEE Symposium on Foundations of Computer Science., IEEE Computer Science Press, Los Alamitos, CA, 323--332.]]"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1007\/PL00012580"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0196-6774(03)00053-1"},{"key":"e_1_2_1_25_1","volume-title":"Proceedings of the 5th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems. 161--174","author":"Halperin E.","unstructured":"Halperin , E. , and Srinivasan , A . 2002. Improved approximation algorithms for the partial vertex cover problem . In Proceedings of the 5th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems. 161--174 .]] Halperin, E., and Srinivasan, A. 2002. Improved approximation algorithms for the partial vertex cover problem. In Proceedings of the 5th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems. 161--174.]]"},{"key":"e_1_2_1_26_1","doi-asserted-by":"crossref","unstructured":"Kalyanasundaram B. Pruhs K. and \n      Velauthapillai M\n  . \n  2000\n  . Scheduling broadcasts in wireless networks. In Proceedings of the European Symposium of Algorithms Lecture Notes in Computer Science vol. \n  1879\n  . \n  Springer-Verlog New York 290--301.]]   Kalyanasundaram B. Pruhs K. and Velauthapillai M. 2000. Scheduling broadcasts in wireless networks. In Proceedings of the European Symposium of Algorithms Lecture Notes in Computer Science vol. 1879. Springer-Verlog New York 290--301.]]","DOI":"10.1007\/3-540-45253-2_27"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01585745"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1018722928191"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.5555\/645413.652135"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539793250767"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579324"},{"key":"e_1_2_1_33_1","unstructured":"SDH. SDH frequently asked questions. http:\/\/www1.biz.biglobe.ne.jp\/~worldnet\/faq\/sdh.html.]]  SDH. SDH frequently asked questions. http:\/\/www1.biz.biglobe.ne.jp\/~worldnet\/faq\/sdh.html.]]"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.5555\/3113606.3113856"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.5555\/874063.875563"},{"key":"e_1_2_1_36_1","unstructured":"Stern T. E. and Bala K. 1999. Multiwavelength optical networks: A layered approach. Prentice-Hall Englewood Cliffs NJ.]]   Stern T. E. and Bala K. 1999. Multiwavelength optical networks: A layered approach. Prentice-Hall Englewood Cliffs NJ.]]"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548398003393"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.172501399"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1147954.1147956","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1147954.1147956","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T19:43:53Z","timestamp":1750275833000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1147954.1147956"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006,5]]},"references-count":37,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2006,5]]}},"alternative-id":["10.1145\/1147954.1147956"],"URL":"https:\/\/doi.org\/10.1145\/1147954.1147956","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2006,5]]},"assertion":[{"value":"2006-05-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}