Buy-at-Bulk Network Design with Protection

References

• Andrews M. Hardness of buy-at-bulk network design. Proc. IEEE Sympos. Foundations Comput. Sci. (2004) (IEEE Computer Society, Washington, DC) 115–124Crossref, Google Scholar
• Andrews M., Zhang L. Approximation algorithms for access network design. Algorithmica (2002) 34(2):197–215Crossref, Google Scholar
• Awerbuch B., Azar Y. Buy-at-bulk network design. Proc. IEEE Sympos. Foundations Comput. Sci. (1997) (IEEE Computer Society, Washington, DC) 542–547Crossref, Google Scholar
• Bartal Y. On approximating arbitrary metrics by tree metrics. Proc. ACM Sympos. Theory Comput. (1998) (ACM, New York) 161–168Crossref, Google Scholar
• Charikar M., Karagiozova A. On non-uniform multicommodity buy-at-bulk network design. Proc. ACM Sympos. Theory Comput. (2005) (ACM, New York) 176–182Crossref, Google Scholar
• Chekuri C., Korula N. Single-sink network design with vertex connectivity requirements. Proc. Foundations of Software Tech. Theoret. Comput. Sci. (2008) (Dagstuhl Publishing, Wadern, Germany) Google Scholar
• Chekuri C., Khanna S., Shepherd F. B. The all-or-nothing multicommodity flow problem. Proc. ACM Sympos. Theory Comput. (2004) (ACM, New York) 156–165Crossref, Google Scholar
• Chekuri C., Hajiaghayi M. T., Kortsarz G., Salavatipour M. R. Approximation algorithms for nonuniform buy-at-bulk network design. SIAM J. Comput. (2010) 39(5):1772–1798Crossref, Google Scholar
• Chekuri C., Claisse P., Essiambre R.-J., Fortune S., Kilper D. C., Lee W., Nithi N. K., et al. Design tools for transparent optical networks. Bell Labs Tech. J. (2006) 11(2):129–143Crossref, Google Scholar
• Chuzhoy J., Khanna S. An O(k3 log n) approximation algorithm for vertex-connectivity survivable network design. Proc. IEEE Sympos. Foundations Comput. Sci. (2009) (IEEE Computer Society, New York) 437–441Google Scholar
• Chuzhoy J., Gupta A., Naor J., Sinha A. On the approximability of some network design problems. ACM Trans. Algorithms (2008) 4(2, Article 23). http://dx.doi.org/10.1145/1361192.1361200Google Scholar
• Fakcharoenphol J., Rao S., Talwar K. A tight bound on approximating arbitrary metrics by tree metrics. J. Comput. System Sci. (2004) 69:485–497Crossref, Google Scholar
• Fleischer L., Jain K., Williamson D. P. An iterative rounding 2-approximation algorithm for the element connectivity problem. J. Comput. System Sci. (2006) 72(5):838–867Crossref, Google Scholar
• Grandoni F., Italiano G. F. Improved approximation for single-sink buy-at-bulk. Proc. Internat. Sympos. Algorithms Comput. (2006) (Springer, Berlin/Heidelberg) 111–120Crossref, Google Scholar
• Guha S., Meyerson A., Munagala K. A constant factor approximation for the single sink edge installation problem. SIAM J. Comput. (2009) 38(6):2426–2442Crossref, Google Scholar
• Gupta A., Krishnaswamy R., Ravi R. Online and stochastic survivable network design. Proc. ACM Sympos. Theory Comput. (2009) (ACM, New York) 685–694Crossref, Google Scholar
• Gupta A., Kumar A., Pál M., Roughgarden T. Approximation via cost-sharing: Simpler and better approximation algorithms for network design. J. ACM (2007) 54(3, Article 11). http://dx.doi.org/10.1145/1236457.1236458Google Scholar
• Hassin R., Ravi R., Salman F. S. Approximation algorithms for a capacitated network design. Algorithmica (2003) 38(3):417–431Crossref, Google Scholar
• Hochbaum D. S.Approximation Algorithms for NP-Hard Problems (1997) (PWS Publishing Company, Boston) Google Scholar
• Jain K. A factor 2 approximation algorithm for the generalized Steiner network problem. Combinatorica (2001) 21(1):39–60Crossref, Google Scholar
• Jothi R., Raghavachari B. Improved approximation algorithms for the single-sink buy-at-bulk network design problem. Proc. Scandinavian Workshop on Algorithm Theory (2004) (Springer, Berlin/Heidelberg) 336–348Crossref, Google Scholar
• Kortsarz G., Nutov Z. Approximating some network design problems with node costs. Proc. Approximation, Randomization Combin. Optim. (2009) (Springer, Berlin/Heidelberg) 231–243Crossref, Google Scholar
• McGregor A., Shepherd B. Island hopping and path colouring, with applications to WDM network design. Proc. ACM-SIAM Sympos. Discrete Algorithms (2007) (SIAM, Philadelphia) 864–873Google Scholar
• Meyerson A., Munagala K., Plotkin S. Cost-distance: Two metric network design. SIAM J. Comput. (2008) 38(4):1648–1659Crossref, Google Scholar
• Ramaswami R., Sivarajan K. N.Optical Networks: A Practical Perspective (2001) 2nd ed.(Morgan Kaufmann, San Francisco) Google Scholar
• Salman F. S., Cheriyan J., Ravi R., Subramanian S. Buy at bulk network design: Approximating the single-sink edge installation problem. SIAM J. Optim. (2000) 11(3):595–610Crossref, Google Scholar
• Schrijver A.Combinatorial Optimization: Polyhedra and Efficiency (2003) (Springer-Verlag, Heidelberg/Berlin) Google Scholar
• Somani A. K.Survivability and Traffic Grooming in WDM Optical Networks (2006) (Cambridge University Press, Oxford, UK) Crossref, Google Scholar
• Stern T. E., Bala K.Multiwavelength Optical Networks: A Layered Approach (1999) (Addison-Wesley, Boston) Google Scholar
• Talwar K. Single-sink buy-at-bulk LP has constant integrality gap. Proc. Integer Programming Combin. Optim. (2002) (Springer, Heidelberg/Berlin) 475–486Crossref, Google Scholar
• Vazirani V. V.Approximation Algorithms (2001) (Springer, Berlin/Heidelberg) Google Scholar
• Williamson D. P., Goemans M. X., Mihail M., Vazirani V. V. A primal-dual approximation algorithm for generalized Steiner network problems. Combinatorica (1995) 15:534–454Crossref, Google Scholar