Dependent rounding and its applications to approximation algorithms

ABSTRACT

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.

REFERENCES

• 1: Ageev, A., and Sviridenko, M. 2004. Pipage rounding: a new method of constructing algorithms with proven performance guarantee. J. Combinat. Optim. 8, 3, 307--328.
• 2: Nikhil Bansal , Moses Charikar , Sanjeev Khanna , Joseph (Seffi) Naor, Approximating the average response time in broadcast scheduling, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
• 3: Bansal, N., Coppersmith, D., and Sviridenko, M. 2004. Improved approximation algorithms for broadcast scheduling. IBM Tech Report RC23468.
• 4: Amotz Bar-Noy , Reuven Bar-Yehuda , Ari Freund , Joseph (Seffi) Naor , Baruch Schieber, A unified approach to approximating resource allocation and scheduling, Journal of the ACM (JACM), v.48 n.5, p.1069-1090, September 2001 [doi>10.1145/502102.502107]
• 5: Amotz Bar-Noy , Sudipto Guha , Yoav Katz , Joseph (Seffi) Naor , Baruch Schieber , Hadas Shachnai, Throughput maximization of real-time scheduling with batching, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.742-751, January 06-08, 2002, San Francisco, California
• 6: Yair Bartal , S. Muthukrishnan, Minimizing maximum response time in scheduling broadcasts, Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms, p.558-559, January 09-11, 2000, San Francisco, California, United States
• 7: Chandra Chekuri , Sanjeev Khanna, A PTAS for the multiple knapsack problem, Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms, p.213-222, January 09-11, 2000, San Francisco, California, United States
• 8: Julia Chuzhoy , Joseph Naor, Covering Problems with Hard Capacities, Proceedings of the 43rd Symposium on Foundations of Computer Science, p.481-489, November 16-19, 2002
• 9: Cooper, C., and Frieze, A. 2003a. Crawling on simple models of web graphs. Internet Math. 1, 57--90.
• 10: Colin Cooper , Alan Frieze, A general model of web graphs, Random Structures & Algorithms, v.22 n.3, p.311-335, May 2003 [doi>10.1002/rsa.10084]
• 11: 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.
• 12: Benjamin Doerr, Non-independent randomized rounding, Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, January 12-14, 2003, Baltimore, Maryland
• 13: 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.
• 14: Thomas Erlebach , Alexander Hall, NP-Hardness of Broadcast Scheduling and Inapproximability of Single-Source Unsplittable Min-Cost Flow, Journal of Scheduling, v.7 n.3, p.223-241, May-June 2004 [doi>10.1023/B:JOSH.0000019682.75022.96]
• 15: Stephen Eubank , V. S. Anil Kumar , Madhav V. Marathe , Aravind Srinivasan , Nan Wang, Structural and algorithmic aspects of massive social networks, Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, January 11-14, 2004, New Orleans, Louisiana
• 16: Shimon Even, Graph Algorithms, W. H. Freeman & Co., New York, NY, 1979
• 17: Michalis Faloutsos , Petros Faloutsos , Christos Faloutsos, On power-law relationships of the Internet topology, Proceedings of the conference on Applications, technologies, architectures, and protocols for computer communication, p.251-262, August 30-September 03, 1999, Cambridge, Massachusetts, United States
• 18: Frieze, S. A. A., and Kaplan, H. 2002. A new rounding procedure for the assignment problem with applications to dense graph arrangement problems. Math. Prog. 92, 1, 1--36.
• 19: Gailis, R., and Khuller, S. Broadcast scheduling with deadlines. http://www.cs.umd.edu/users/samir/grant/renars.ps.
• 20: 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.
• 21: Rajiv Gandhi , Samir Khuller , Yoo-Ah Kim , Yung-Chun (Justin) Wan, Algorithms for Minimizing Response Time in Broadcast Scheduling, Algorithmica, v.38 n.4, p.597-608, January 2004 [doi>10.1007/s00453-003-1058-x]
• 22: Rajiv Gandhi , Samir Khuller , Srinivasan Parthasarathy , Aravind Srinivasan, Dependent Rounding in Bipartite Graphs, Proceedings of the 43rd Symposium on Foundations of Computer Science, p.323-332, November 16-19, 2002
• 23: Graham, F. C., and Lu, L. 2002. Connected components in random graphs with given degree sequences. Annals of Combinatorics 6, 125--145.
• 24: Sudipto Guha , Refael Hassin , Samir Khuller , Einat Or, Capacitated vertex covering, Journal of Algorithms, v.48 n.1, p.257-270, August 2003 [doi>10.1016/S0196-6774(03)00053-1]
• 25: Eran Halperin , Aravind Srinivasan, Improved Approximation Algorithms for the Partial Vertex Cover Problem, Proceedings of the 5th International Workshop on Approximation Algorithms for Combinatorial Optimization, p.161-174, September 17-21, 2002
• 26: Bala Kalyanasundaram , Kirk Pruhs , Mahendran Velauthapillai, Scheduling Broadcasts in Wireless Networks, Proceedings of the 8th Annual European Symposium on Algorithms, p.290-301, September 05-08, 2000
• 27: Jon Michael Kleinberg , Michel X. Goemans, Approximation algorithms for disjoint paths problems, 1996
• 28: J. K. Lenstra , D. B. Shmoys , É. Tardos, Approximation algorithms for scheduling unrelated parallel machines, Mathematical Programming: Series A and B, v.46 n.3, p.259-271, Apr. 1990 [doi>10.1007/BF01585745]
• 29: Dimitris Logothetis , Kishor Trivedi, The Effect of Detection and Restoration Times forError Recovery in Communication Networks, Journal of Network and Systems Management, v.5 n.2, p.173-195, June 01, 1997 [doi>10.1023/A:1018722928191 ]
• 30: Michael Luby, LT Codes, Proceedings of the 43rd Symposium on Foundations of Computer Science, p.271, November 16-19, 2002
• 31: Alessandro Panconesi , Aravind Srinivasan, Randomized Distributed Edge Coloring via an Extension of the Chernoff--Hoeffding Bounds, SIAM Journal on Computing, v.26 n.2, p.350-368, April 1997 [doi>10.1137/S0097539793250767]
• 32: Prabhakar Raghavan , Clark D. Tompson, Randomized rounding: a technique for provably good algorithms and algorithmic proofs, Combinatorica, v.7 n.4, p.365-374, Dec, 1987 [doi>10.1007/BF02579324]
• 33: SDH. SDH frequently asked questions. http://www1.biz.biglobe.ne.jp/~worldnet/faq/sdh.html.
• 34: David B. Shmoys , Éva Tardos, An approximation algorithm for the generalized assignment problem, Mathematical Programming: Series A and B, v.62 n.3, p.461-474, Dec. 8, 1993 [doi>10.1007/BF01585178]
• 35: A. Srinivasan, Distributions on Level-Sets with Applications to Approximation Algorithms, Proceedings of the 42nd IEEE symposium on Foundations of Computer Science, p.588, October 14-17, 2001
• 36: Thomas E. Stern , Krishna Bala, Multiwavelength Optical Networks: A Layered Approach, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1999
• 37: William T. Trotter , Peter Winkler, Ramsey Theory and Sequences of Random Variables, Combinatorics, Probability and Computing, v.7 n.2, p.221-238, June 1998 [doi>10.1017/S0963548398003393]
• 38: Yook, S., Jeong, H., and Barabasi, A. 2002. Modeling the internet's large-scale topology. Proc. Nati. Acad. Sci. 99, 13382--13386.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems

Additional Classification:
  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Probabilistic algorithms (including Monte Carlo)

General Terms:
Algorithms, Theory

Keywords:
Randomized rounding, broadcast scheduling