Network design for information networks

ABSTRACT

We define a new class of network design problems motivated by designing information networks. In our model, the cost of transporting flow for a set of users (or servicing them by a facility) depends on the amount of information requested by the set of users. We assume that the aggregation cost follows economies of scale, that is, the incremental cost of a new user is less if the set of users already served is larger. Naturally, information requested by some sets of users might aggregate better than that of others, so our cost is now a function of the actual set of users. not just their total demand.We provide constant-factor approximation algorithms to two important problems in this general model. In the Group Facility Location problem, each user needs information about a resource. and the cost is a linear function of the number of resources involved (instead of the number of clients served). The Dependent Maybecast Problem extends the Karger-Minkoff maybecast model to probabilities with limited correlation and also contains the 2-stage stochastic optimization problem as a special case. We also give an O(ln n)-approximation algorithm for the Single Sink Information Network Design problem.We show that the Stochastic Steiner Tree problem can be approximated by dependent maybecast, and using this we obtain an O(1)-approximation algorithm for the k-stage stochastic Steiner tree problem for any fixed k. This is the first approximation algorithm for multi-stage stochastic optimization. Our algorithm allows scenarios to have different inflation factors, and works for any distribution provided that we can sample the distribution.

REFERENCES

• 1: Ajit Agrawal , Philip Klein , R. Ravi, When Trees Collide: An Approximation Algorithm for theGeneralized Steiner Problem on Networks, SIAM Journal on Computing, v.24 n.3, p.440-456, June 1995 [doi>10.1137/S0097539792236237]
• 2: B. Awerbuch , Y. Azar, Buy-at-bulk network design, Proceedings of the 38th Annual Symposium on Foundations of Computer Science (FOCS '97), p.542, October 19-22, 1997
• 3: Alexis Campailla , Sagar Chaki , Edmund Clarke , Somesh Jha , Helmut Veith, Efficient filtering in publish-subscribe systems using binary decision diagrams, Proceedings of the 23rd International Conference on Software Engineering, p.443-452, May 12-19, 2001, Toronto, Ontario, Canada
• 4: Jittat Fakcharoenphol , Satish Rao , Kunal Talwar, A tight bound on approximating arbitrary metrics by tree metrics, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, June 09-11, 2003, San Diego, CA, USA [doi>10.1145/780542.780608]
• 5: Ashish Goel , Deborah Estrin, Simultaneous optimization for concave costs: single sink aggregation or single source buy-at-bulk, Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, January 12-14, 2003, Baltimore, Maryland
• 6: Michel X. Goemans , David P. Williamson, A General Approximation Technique for Constrained Forest Problems, SIAM Journal on Computing, v.24 n.2, p.296-317, April 1995 [doi>10.1137/S0097539793242618]
• 7: Anupam Gupta , Amit Kumar , Martin Pál , Tim Roughgarden, Approximation Via Cost-Sharing: A Simple Approximation Algorithm for the Multicommodity Rent-or-Buy Problem, Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science, p.606, October 11-14, 2003
• 8: Anupam Gupta , Martin Pál , R. Ravi , Amitabh Sinha, Boosted sampling: approximation algorithms for stochastic optimization, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, June 13-16, 2004, Chicago, IL, USA [doi>10.1145/1007352.1007419]
• 9: Anupam Gupta , R. Ravi , Amitabh Sinha, An Edge in Time Saves Nine: LP Rounding Approximation Algorithms for Stochastic Network Design, Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science (FOCS'04), p.218-227, October 17-19, 2004 [doi>10.1109/FOCS.2004.11]
• 10: Kamal Jain , Vijay V. Vazirani, Approximation algorithms for metric facility location and k-Median problems using the primal-dual schema and Lagrangian relaxation, Journal of the ACM (JACM), v.48 n.2, p.274-296, March 2001 [doi>10.1145/375827.375845]
• 11: D. R. Karget , M. Minkoff, Building Steiner trees with incomplete global knowledge, Proceedings of the 41st Annual Symposium on Foundations of Computer Science, p.613, November 12-14, 2000
• 12: Ravi Ramamoorthi , Amitabh Sinha, Integrated Logistics: Approximation Algorithms Combining Facility Location and Network Design, Proceedings of the 9th International IPCO Conference on Integer Programming and Combinatorial Optimization, p.212-229, May 27-29, 2002
• 13: R. Ravi , A. Sinha, Multicommodity facility location, Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, January 11-14, 2004, New Orleans, Louisiana
• 14: David B. Shmoys , Chaitanya Swamy, Stochastic Optimization is (Almost) as easy as Deterministic Optimization, Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science (FOCS'04), p.228-237, October 17-19, 2004 [doi>10.1109/FOCS.2004.62]
• 15: David B. Shmoys , Chaitanya Swamy , Retsef Levi, Facility location with Service Installation Costs, Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, January 11-14, 2004, New Orleans, Louisiana
• 16: Chaitanya Swamy , Amit Kumar, Primal–Dual Algorithms for Connected Facility Location Problems, Algorithmica, v.40 n.4, p.245-269, September 2004 [doi>10.1007/s00453-004-1112-3]