Stochastic Combinatorial Optimization with Controllable Risk Aversion Level

References

• Beale E. M. L. On minimizing a convex function subject to linear inequalities. J. Roy. Statist. Soc., Ser. B (Methodological) (1955) 17(2):173–184Google Scholar
• Ben-Tal A., Teboulle M. An old-new concept of convex risk measures: The optimized certainty equivalent. Math. Finance (2007) 17(3):449–476Crossref, Google Scholar
• Charikar M., Chekuri C., Pál M., Chekuri C., Jansen K., Rolim J. D. P., Trevisan L. Sampling bounds for stochastic optimization. Proc. 9th Internat. Workshop on Randomization Comput. (2005) 3624(Springer, Berlin/Heidelberg) 257–269Lecture Notes in Computer ScienceCrossref, Google Scholar
• Chvátal V. A greedy heuristic for the set-covering problem. Math. Oper. Res. (1979) 4(3):233–235Link, Google Scholar
• Dantzig G. B. Linear programming under uncertainty. Management Sci. (1955) 1(3/4):197–206Link, Google Scholar
• Dhamdhere K., Goyal V., Ravi R., Singh M. How to pay, come what may: Approximation algorithms for demand-robust covering problems. Proc. 46th Annual IEEE Sympos. Foundations Comput. Sci. (2005) 367–378Crossref, Google Scholar
• Dye S., Stougie L., Tomasgard A. The stochastic single resource service-provision problem. Naval Res. Logist. (2003) 50(8):869–887Crossref, Google Scholar
• Feige U., Jain K., Mahdian M., Mirrokni V., Fischetti M., Williamson D. P. Robust combinatorial optimization with exponential scenarios. Proc. 12th Internat. Conf. Integer Programming Combin. Optim. (2007) 4513(Springer, Berlin/Heidelberg) 439–453Lecture Notes in Computer ScienceCrossref, Google Scholar
• Grötschel M., Lovász L., Schrijver A.Geometric Algorithms and Combinatorial Optimization, 2nd corrected ed. Algorithms and Combinatorics (1993) 2(Springer-Verlag, Berlin/Heidelberg) Crossref, Google Scholar
• Gupta A., Ravi R., Sinha A. LP rounding approximation algorithms for stochastic network design. Math. Oper. Res. (2007) 32(2):345–364Link, Google Scholar
• Gupta A., Pál M., Ravi R., Sinha A. Boosted sampling: Approximation algorithms for stochastic optimization. Proc. 36th Annual ACM Sympos. Theory Comput. (2004) (ACM, New York) 417–426Crossref, Google Scholar
• Hoeffding W. Probability inequalities for sums of bounded random variables. J. Amer. Statist. Assoc. (1963) 58(301):13–30Crossref, Google Scholar
• Immorlica N., Karger D., Minkoff M., Mirrokni V. On the costs and benefits of procrastination: Approximation algorithms for stochastic combinatorial optimization problems. Proc. 15th Annual ACM-SIAM Sympos. Discrete Algorithms (2004) (SIAM, Philadelphia) 691–700Google Scholar
• Kleywegt A. J., Shapiro A., Homem-De-Mello T. The sample average approximation method for stochastic discrete optimization. SIAM J. Optim. (2001) 12(2):479–502Crossref, Google Scholar
• Lax P. D.Functional Analysis. Pure and Applied Mathematics: A Wiley-Interscience Series of Texts, Monographs, and Tracts (2002) (John Wiley & Sons, Inc., New York) Google Scholar
• Nemhauser G. L., Trotter L. E. Properties of vertex packing and independence system polyhedra. Math. Programming (1974) 6:48–61Crossref, Google Scholar
• Nesterov Y., Nemirovskii A.Interior-Point Polynomial Algorithms in Convex Programming. SIAM Studies in Applied Mathematics (1994) 13(SIAM, Philadelphia) Crossref, Google Scholar
• Ravi R., Sinha A. Hedging uncertainty: Approximation algorithms for stochastic optimization problems. Math. Programming, Ser. A (2006) 108(1):97–114Crossref, Google Scholar
• Rockafellar R. T., Uryasev S. Conditional value-at-risk for general loss distributions. J. Banking Finance (2002) 26(7):1443–1471Crossref, Google Scholar
• Ruszczyński A., Shapiro A., Calafiore G., Dabbene F. Optimization of risk measures. Probabilistic and Randomized Methods for Design Under Uncertainty (2005) (Springer-Verlag, London) 119–157Google Scholar
• Shapiro A., Nemirovski A., Jeyakumar V., Rubinov A. On complexity of stochastic programming problems. Continuous Optimization: Current Trends and Modern Applications, Applied Optimization (2005) 99(Springer Science+Business Media Inc., New York) 111–146Crossref, Google Scholar
• Shmoys D. B., Swamy C. An approximation scheme for stochastic linear programming and its application to stochastic integer programs. J. ACM (2006) 53(6):978–1012Crossref, Google Scholar
• Shmoys D. B., Tardos É., Aardal K. Approximation algorithms for facility location problems. Proc. 29th Annual ACM Sympos. Theory of Comput. (1997) (ACM, New York) 265–274Google Scholar
• So A. M.-C., Zhang J., Ye Y., Díaz J., Jansen K., Rolim J. D. P., Zwick U. Stochastic combinatorial optimization with controllable risk aversion level. Proc. 9th Internat. Workshop Approximation Algorithms for Combin. Optim. Problems (2006) 4110(Springer, Berlin/Heidelberg) 224–235Lecture Notes in Computer ScienceCrossref, Google Scholar
• Swamy C., Shmoys D. B. Sampling-based approximation algorithms for multi-stage stochastic optimization. Proc. 46th Annual IEEE Sympos. Foundations Comput. Sci. (2005) 357–366Google Scholar
• Vazirani V. V.Approximation Algorithms (2001) (Springer-Verlag, Berlin) Google Scholar