AbstractSeveral practical instances of network design problems often require the network to satisfy multiple constraints. In this paper, we focus on the following problem (and its variants): find a low-cost network,under one cost function, that services every node in the graph, under another cost function, (i.e., every node of the graph is within a prespecified distance from the network). Such problems find applications in optical network design and the efficient maintenance of distributed databases.
We utilize the framework developed in Marathe et al. [1995] (Marathe, M. V., Ravi, R., Sundaram, R., Ravi, S. S., Rosenkrantz, D. J., and B., Hunt H. 1995. Bicriteria network design problems. In Proceedings of the International Colloquium on Automata, Languages and Programming, LNCS 944, 487-498.) to formulate these problems as bicriteria network design problems, and present approximation algorithms for a class of service-constrained network design problems. We also present lower bounds on the approximability of these problems that demonstrate that our performance ratios are close to best possible.
Categories and Subject Descriptors: G.2.2 [Discrete Mathematics]: Graph Theory
Additional Key Words and Phrases: approximation algorithms, bicriteria problems, spanning trees, network design, combinatorial algorithms
Selected papers that cite this one
- Naveen Garg, Goran Konjevod, and R. Ravi. A polylogarithmic approximation algorithm for the group Steiner tree problem. In Proceedings of the Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 253-259, San Francisco, California, 25-27 January 1998.
- Aravind Srinivasan and Chung-Piaw Teo. A constant-factor approximation algorithm for packet routing, and balancing local vs. global criteria. In Proceedings of the Twenty-Ninth Annual ACM Symposium on Theory of Computing, pages 636-643, El Paso, Texas, 4-6 May 1997.
Selected references
- Ajit Agrawal, Philip Klein, and R. Ravi. When trees collide: An approximation algorithm for the generalized Steiner problem on networks. SIAM Journal on Computing, 24(3):440-456, June 1995.
- Baruch Awerbuch, Yair Bartal, and Amos Fiat. Competitve distributed file allocation. In Proceedings of the Twenty-Fifth Annual ACM Symposium on the Theory of Computing, pages 164-173, San Diego, California, 16-18 May 1993.
- Yair Bartal, Amos Fiat, and Yuval Rabani. Competitive algorithms for distributed data management (extended abstract). In Proceedings of the Twenty-Fourth Annual ACM Symposium on the Theory of Computing, pages 39-50, Victoria, British Columbia, Canada, 4-6 May 1992.
- Avrim Blum, R. Ravi, and Santosh Vempala. A constant-factor approximation algorithm for the k-MST problem (extended abstract). In Proceedings of the Twenty-Eighth Annual ACM Symposium on the Theory of Computing, pages 442-448, Philadelphia, Pennsylvania, 22-24 May 1996.
- Lawrence W. Dowdy and Derrell V. Foster. Comparative models of the file assignment problem. ACM Computing Surveys, 14(2):287-313, June 1982.
- Uriel Feige. A threshold of ln n for approximating set cover (preliminary version). In Proceedings of the Twenty-Eighth Annual ACM Symposium on the Theory of Computing, pages 314-318, Philadelphia, Pennsylvania, 22-24 May 1996.
- Akhil Kumar and Arie Segev. Cost and availability tradeoffs in replicated data concurrency control. ACM Transactions on Database Systems, 18(1):102-131, March 1993.
- Ouri Wolfson and Amir Milo. The multicast policy and its relationship to replicated data placement. ACM Transactions on Database Systems, 16(1):181-205, March 1991.