LP Rounding Approximation Algorithms for Stochastic Network Design

References

• Agrawal Ajit, Klein Philip, Ravi R. When trees collide: An approximation algorithm for the generalized Steiner problem on networks. SIAM J. Comput. (1995) 24(3):440–456(Preliminary version in 23rd STOC, 1991.)Crossref, Google Scholar
• Awerbuch Baruch, Azar Yossi. Buy-at-bulk network design. Proc. 38th Annual IEEE Sympos. Foundations Comput. Sci., Miami, FL (1997) 542–547IEEE Computer SocietyCrossref, Google Scholar
• Beale E. M. L. On minimizing a convex function subject to linear inequalities. J. Roy. Statist. Soc. Ser. B. (1955) 17:173–184discussion, 194–203. (Symposium on linear programming.)Google Scholar
• Birge John R., Louveaux François. Introduction to Stochastic Programming. Springer Series in Operations Research (1997) (Springer-Verlag, New York) Google Scholar
• Dantzig George B. Linear programming under uncertainty. Management Sci. (1955) 1:197–206Link, Google Scholar
• Dye Shane, Stougie Leen, Tomasgard Asgeir. The stochastic single resource service-provision problem. Naval Res. Logist. (2003) 50(8):869–887Crossref, Google Scholar
• Garg Naveen, Khandekar Rohit, Konjevod Goran, Ravi R., Salman F. Sibel, Sinha Amitabh. On the integrality gap of a natural formulation of the single-sink buy-at-bulk network design formulation. Proc. 8th Integer Programming Combin. Optim. Conf., Utrecht, The Netherlands, Lecture Notes in Computer Science (2001) 2081(Springer)170–184Google Scholar
• Goemans Michel X., Williamson David P. A general approximation technique for constrained forest problems. SIAM J. Comput. (1995) 24(2):296–317Crossref, Google Scholar
• Guha Sudipto, Meyerson Adam, Mungala Kamesh. A constant factor approximation for the single sink edge installation problems. Proc. 33rd Annual ACM Sympos. Theory Comput. (STOC), Crete, Greece (2001) (ACM Press, New York) 383–388Crossref, Google Scholar
• Gupta Anupam, Kumar Amit, Roughgarden Tim. Simpler and better approximation algorithms for network design. Proc. 35th Annual ACM Sympos. Theory Comput., San Diego, CA (2003) (ACM Press, New York) 365–372Crossref, Google Scholar
• Gupta Anupam, Ravi R., Sinha Amitabh. An edge in time saves nine: LP rounding approximation algorithms for stochastic network design. Proc. 45th Annual IEEE Sympos. Foundations Comput. Sci., Rome, Italy (2004) (IEEE Computer Society)218–227Crossref, Google Scholar
• Gupta Anupam, Pál Martin, Ravi R., Sinha Amitabh. Boosted sampling: Approximation algorithms for stochastic optimization problems. Proc. 36th Annual ACM Sympos. Theory Comput., Chicago, IL (2004) (ACM Press, New York) 417–425Crossref, Google Scholar
• Gupta Anupam, Pál Martin, Ravi R., Sinha Amitabh. What about Wednesday? Approximation algorithms for multistage stochastic optimization. Proc. 9th Internat. Workshop Approximation Algorithms Combin. Optim. Problems (APPROX), Berkeley, CA (2005) (Springer)86–98Crossref, Google Scholar
• Gupta Anupam, Kumar Amit, Kleinberg Jon, Rastogi Rajeev, Yener Bülent. Provisioning a virtual private network: A network design problem for multicommodity flow. Proc. 33rd Annual ACM Sympos. Theory Comput., Crete, Greece (2001) (ACM Press, New York) 389–398Crossref, Google Scholar
• Hassin Refael, Ravi R., Salman F. S. Approximation algorithms for a capacitated network design problem. Internat. Workshop on Approximation Algorithms for Combin. Optim. Problems (APPROX), Saarbrücken, Germany (2000) (Springer)167–176Crossref, Google Scholar
• Hayrapetyan Ara, Swamy Chaitanya, Tardos Éva. Network design for information networks. Proc. 15th Annual ACM-SIAM Sympos. Discrete Algorithms, Vancouver, Canada (2005) (SIAM, Philadelphia, PA) 933–942Google Scholar
• Immorlica Nicole, Karger David, Minkoff Maria, Mirrokni Vahab. On the costs and benefits of procrastination: Approximation algorithms for stochastic combinatorial optimization problems. Proc. 15th Annual ACM-SIAM Sympos. Discrete Algorithms, New Orleans, LA (2004) (SIAM, Philadelphia, PA) 684–693Google Scholar
• Kall Peter, Wallace Stein W.Stochastic Programming. Wiley-Interscience Series in Systems and Optimization (1994) (John Wiley & Sons Ltd., Chichester, UK) Google Scholar
• Khuller Samir, Raghavachari Balaji, Young Neal E. Balancing minimum spanning and shortest path trees. Algorithmica (1995) 14(4):305–322Crossref, Google Scholar
• Klein Haneveld Willem K., van der Vlerk Maarten H. Stochastic integer programming: General models and algorithms. Ann. Oper. Res. (1999) 85:39–57Crossref, Google Scholar
• Klein Haneveld Willem K., van der Vlerk Maarten H.Stochastic Programming (2003) (Department of Econometrics, University of Groningen, Netherlands) Google Scholar
• Mansour Yishay, Peleg David. An approximation algorithm for minimum-cost network design. Robust Communication Networks: Interconnection and Survivability (New Brunswick, NJ, 1998) (2000) 53(American Mathematical Society, Providence, RI) 97–106DIMACS Series in Discrete Mathematics and Theoretical Computer ScienceCrossref, Google Scholar
• Ravi R., Salman F. S. Approximation algorithms for the traveling purchaser problem and its variants in network design. Algorithms—ESA ’99 (Prague), Lecture Notes in Computer Science (1999) 1643(Springer, Berlin, Germany) 29–40Crossref, Google Scholar
• Ravi R., Sinha Amitabh. Hedging uncertainty: Approximation algorithms for stochastic optimization problems. Math. Programming A (2006) 108(1):97–114Crossref, Google Scholar
• Robins Gabriel, Zelikovsky Alexander. Improved Steiner tree approximation in graphs. Proc. 11th Annual ACM-SIAM Sympos. Discrete Algorithms, San Francisco, CA (2000) (SIAM, Philadelphia, PA) 770–779Google Scholar
• Salman F. Sibel, Cheriyan Joseph, Ravi R., Subramanian Sairam. Buy-at-bulk network design: Approximating the single-sink edge installation problem. Proc. 8th Annual ACM-SIAM Sympos. Discrete Algorithms, New Orleans, LA (1997) (SIAM, Philadelphia, PA) 619–628Google Scholar
• Shmoys David, Swamy Chaitanya. Stochastic optimization is (almost) as easy as deterministic optimization. Proc. 45th Annual IEEE Sympos. Foundations of Comput. Sci., Rome, Italy (2004) (IEEE Computer Society)228–237Crossref, Google Scholar
• Talwar Kunal. Single-sink buy-at-bulk LP has constant integrality gap. Proc. 9th Integer Programming Combin. Optim. Conf., Cambridge, MA, Lecture Notes in Computer Science (2002) 2337(Springer)475–486Crossref, Google Scholar
• Vazirani Vijay V.Approximation Algorithms (2001) (Springer-Verlag, Berlin, Germany) Google Scholar