From Uncertainty to Nonlinearity: Solving Virtual Private Network via Single-Sink Buy-at-Bulk

References

• Bartal Y. On approximating arbitrary metrics by tree metrics. Sympos. Theory Comput. (STOC) (1998) (ACM, New York) 161–168Crossref, Google Scholar
• Becchetti L., Könemann J., Leonardi S., Pál M. Sharing the cost more efficiently: Improved approximation for multicommodity rent-or-buy. ACM Trans. Algorithms (2007) 3(2). Article 23Crossref, Google Scholar
• Byrka J., Grandoni F., Rothvoß T., Sanità L. An improved LP-based approximation for Steiner tree. Sympos. Theory Comput. (STOC) (2010) (ACM, New York) 583–592Crossref, Google Scholar
• Chekuri C. Routing and network design with robustness to changing or uncertain traffic demands. SIGACT News (2007) 38(3):106–128Crossref, Google Scholar
• Chlebik M., Chlebikova J. Approximation hardness of the Steiner tree problem on graphs. Scandinavian Workshop on Algorithm Theory (SWAT) (2002) (Springer, Berlin) 170–179Crossref, Google Scholar
• Cook W., Cunningham W., Pulleyblank W., Schrijver A.Combinatorial Optimization (1998) (John Wiley & Sons Inc., New York) Google Scholar
• Duffield N. G., Goyal P., Greenberg A., Mishra P., Ramakrishnan K. K., van der Merwe J. E. A flexible model for resource management in virtual private networks. SIGCOMM (1999) (ACM, New York) 95–108Crossref, Google Scholar
• Eisenbrand F., Grandoni F. An improved approximation algorithm for virtual private network design. Sympos. Discrete Algorithms (SODA) (2005) (SIAM, Philadelphia) 928–932Google Scholar
• Eisenbrand F., Grandoni F., Oriolo G., Skutella M. New approaches for virtual private network design. SIAM J. Comput. (2007) 37(3):706–721Crossref, Google Scholar
• Eisenbrand F., Grandoni F., Rothvoß T., Schäfer G. Connected facility location via random facility sampling and core detouring. J. Comput. System Sci. (2010) 76:709–726Crossref, Google Scholar
• Erlebach T., Rüegg M. Optimal bandwidth reservation in hose-model VPNs with multi-path routing. Annual Joint Conf. IEEE Comput. Comm. Soc. (INFOCOM) (2004) (IEEE, Piscataway, NJ) 2275–2282Crossref, Google Scholar
• Fakcharoenphol J., Rao S., Talwar K. A tight bound on approximating arbitrary metrics by tree metrics. J. Comput. System Sci. (2004) 69(4):485–497Crossref, Google Scholar
• Fingerhut J., Suri S., Turner J. Designing least-cost nonblocking broadband networks. J. Algorithms (1997) 24(2):287–309Crossref, Google Scholar
• Fiorini S., Oriolo G., Sanità L., Theis D. The VPN problem with concave costs. SIAM J. Discrete Math. (2010) 24(3):1080–1090Crossref, Google Scholar
• Fleischer L., Könemann J., Leonardi S., Schäfer G. Simple cost sharing schemes for multicommodity rent-or-buy and stochastic steiner tree. Sympos. Theory Comput. (STOC) (2006) (ACM, New York) 663–670Crossref, Google Scholar
• Garg N., Gupta A., Leonardi S., Sankowski P. Stochastic analyses for online combinatorial optimization problems. Sympos. Discrete Algorithms (SODA) (2008) (SIAM, Philadelphia) 942–951Google Scholar
• Garg N., Khandekar R., Konjevod G., Ravi R., Salman F., Sinha A. On the integrality gap of a natural formulation of the single-sink buy-at-bulk network design problem. Internat. Conf. Integer Programming Combin. Optim. (IPCO) (2001) (Springer, Berlin) 170–184Crossref, Google Scholar
• Goyal N., Olver N., Shepherd F. B. The VPN conjecture is true. Sympos. Theory Comput. (STOC) (2008) (ACM, New York) 443–450Crossref, Google Scholar
• Grandoni F., Italiano G. F. Improved approximation for single-sink buy-at-bulk. Internat. Sympos. Algorithms Comput. (ISAAC) (2006) (Springer, Berlin) 111–120Crossref, Google Scholar
• Grandoni F., Rothvoß T. Network design via core detouring for problems without a core. Internat. Colloquium on Automata, Languages and Programming (ICALP) (2010) (Springer, Berlin) 490–502Crossref, Google Scholar
• Grandoni F., Kaibel V., Oriolo G., Skutella M. A short proof of the VPN tree routing conjecture on ring networks. Oper. Res. Lett. (2008) 36(3):361–365Crossref, 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., Pál M. Stochastic Steiner trees without a root. Internat. Colloquium on Automata, Languages and Programming (ICALP) (2005) (Springer, Berlin) 1051–1063Crossref, Google Scholar
• Gupta A., Kumar A., Roughgarden T. Simpler and better approximation algorithms for network design. Sympos. Theory Comput. (STOC) (2003) (ACM, New York) 365–372Crossref, Google Scholar
• Gupta A., Kumar A., Pal M., Roughgarden T. Approximation via cost-sharing: Simpler and better approximation algorithms for network design. J. ACM (2007) 54(3). Article 11Crossref, Google Scholar
• Gupta A., Kleinberg J., Kumar A., Rastogi R., Yener B. Provisioning a virtual private network: A network design problem for multicommodity flow. Sympos. Theory Comput. (STOC) (2001) (ACM, New York) 389–398Crossref, Google Scholar
• Hurkens A. J., Keijsper J. C. M., Stougie L. Virtual private network design: A proof of the tree routing conjecture on ring networks. SIAM J. Discrete Math. (2007) 21(2):482–503Crossref, Google Scholar
• Italiano G. F., Leonardi S., Oriolo G. Design of trees in the hose model: The balanced case. Oper. Res. Lett. (2006) 34(6):601–606Crossref, Google Scholar
• Jothi R., Raghavachari B. Improved approximation algorithms for the single-sink buy-at-bulk network design problems. Scandinavian Workshop on Algorithm Theory (SWAT) (2004) (Springer, Berlin) 336–348Crossref, Google Scholar
• Karger D. R., Minkoff M. Building Steiner trees with incomplete global knowledge. Sympos. Foundations Comput. Sci. (FOCS) (2000) (IEEE Computer Society, Piscataway, NJ) 613–623Google Scholar
• Meyerson A., Munagala K., Plotkin S. Cost-distance: Two metric network design. Sympos. Foundations Comput. Sci. (FOCS) (2000) (IEEE Computer Society, Piscataway, NJ) 624–630Crossref, Google Scholar
• Rothvoß T., Sanità L. On the complexity of the asymmetric VPN problem. Internat. Workshop on Approximation Algorithms Combin. Optimi. Problems (APPROX) (2009) (Springer, Berlin) 326–338Crossref, Google Scholar
• Sanità L. Robust network design. (2009) . Ph.D. thesis, Università Sapienza di Roma, RomeGoogle Scholar
• Schrijver A.Combinatorial Optimization. Polyhedra and Efficiency (2003) (Springer-Verlag, Berlin) Google Scholar
• Shmoys D. B., Talwar K. A constant approximation algorithm for the a priori traveling salesman problem. Internat. Conf. Integer Programming Combin. Optim. (IPCO) (2008) (Springer, Berlin) 331–343Crossref, Google Scholar
• Swamy C., Kumar A. Primal-dual algorithms for connected facility location problems. Internat. Workshop on Approximation Algorithms Combin. Optim. Problems (APPROX) (2002) (Springer, Berlin) 256–269Crossref, Google Scholar
• Talwar K. The single-sink buy-at-bulk LP has constant integrality gap. Internat. Conf. Integer Programming Combin. Optim. (IPCO) (2002) (Springer, Berlin) 475–486Crossref, Google Scholar
• van Zuylen A. Deterministic sampling algorithms for network design. Eur. Sympos. Algorithms (ESA) (2008) (Springer, Berlin) 830–841Crossref, Google Scholar