More Web Proxy on the site http://driver.im/

Article

Approximation algorithms for reliable stochastic combinatorial optimization

Author:

Evdokia NikolovaAuthors Info & Claims

APPROX/RANDOM'10: Proceedings of the 13th international conference on Approximation, and 14 the International conference on Randomization, and combinatorial optimization: algorithms and techniques

Pages 338 - 351

Published: 01 September 2010 Publication History

Abstract

We consider optimization problems that can be formulated as minimizing the cost of a feasible solution w^T x over an arbitrary combinatorial feasible set F ⊂ {0, 1}ⁿ. For these problems we describe a broad class of corresponding stochastic problems where the cost vector W has independent random components, unknown at the time of solution. A natural and important objective that incorporates risk in this stochastic setting is to look for a feasible solution whose stochastic cost has a small tail or a small convex combination of mean and standard deviation. Our models can be equivalently reformulated as nonconvex programs for which no efficient algorithms are known. In this paper, we make progress on these hard problems.

Our results are several efficient general-purpose approximation schemes. They use as a black-box (exact or approximate) the solution to the underlying deterministic problem and thus immediately apply to arbitrary combinatorial problems. For example, from an available δ-approximation algorithm to the linear problem, we construct a δ(1 + ε)-approximation algorithm for the stochastic problem, which invokes the linear algorithm only a logarithmic number of times in the problem input (and polynomial in 1/ε), for any desired accuracy level ε > 0. The algorithms are based on a geometric analysis of the curvature and approximability of the nonlinear level sets of the objective functions.

References

[1]

Ackermann, H., Newman, A., Röglin, H., Vöcking, B.: Decision making based on approximate and smoothed pareto curves. In: Deng, X., Du, D.-Z. (eds.) ISAAC 2005. LNCS, vol. 3827, pp. 675-684. Springer, Heidelberg (2005).

Digital Library

[2]

Atamtürk, A., Narayanan, V.: Polymatroids and risk minimization in discrete optimization. Operations Research Letters 36, 618-622 (2008).

Digital Library

[3]

Berstein, Y., Lee, J., Onn, S., Weismantel, R.: Nonlinear optimization for matroid intersection and extensions. Manuscript at arXiv:0807.3907 (2008).

[4]

Bertsekas, D., Nedic, A., Ozdaglar, A.: Convex Analysis and Optimization. Athena Scientific, Belmont (2003).

[5]

Bertsimas, D., Brown, D., Caramanis, C.: Theory and applications of robust optimization (2007) (manuscript).

[6]

Bertsimas, D., Sim, M.: Robust discrete optimization and network flows (2004) (manuscript).

[7]

Chen, A., Ji, Z.: Path finding under uncertainty. Journal of advanced transportation 39(1), 19-37 (2005).

[8]

Dean, B., Goemans, M.X., Vondrák, J.: Approximating the stochastic knapsack: the benefit of adaptivity. In: Proceedings of the 45th Annual Symposium on Foundations of Computer Science, pp. 208-217 (2004).

Digital Library

[9]

Fan, Y., Ka laba, R., Moore, I.J.E.: Arriving on time. Journal of Optimization Theory and Applications 127(3), 497-513 (2005).

[10]

Federal Highway Administration: Traffic Congestion and Reliability: Trends and advanced strategies for congestion mitigation. Cambridge Systematics Inc., Texas Transportation Institute (2005).

[11]

Föllmer, H., Schied, A.: Stochastic Finance: An Introduction in Discrete Time. Walter de Gruyter, Berlin (2004).

[12]

Ghaoui, L.E., Oks, M., Oustry, F.: Worst-case value-at-risk and robust portfolio optimization: A conic programming approach. Oper. Res. 51(4), 543-556 (2003).

Digital Library

[13]

Goel, A., Indyk, P.: Stochastic load balancing and related problems. In: Proceedings of the 40th Symposium on Foundations of Computer Science (1999).

Digital Library

[14]

Goyal, V.: An FPTAS for minimizing a class of quasi-concave functions over a convex set. Technical Report Tepper WP 2008-E24, Carnegie Mellon University Tepper School of Business (2008).

[15]

Grimmett, G., Stirzaker, D.: Probability and Random Processes, 3rd edn. Oxford Univ. Press, Oxford (2001).

[16]

Gupta, A., Pál, M., Ravi, R., Sinha, A.: Boosted sampling: approximation algorithms for stochastic optimization. In: Proceedings of the 36th Annual ACM Symposium on Theory of Computing, Chicago, IL, USA, pp. 365-372 (2004).

Digital Library

[17]

Gupta, A., Pál, M., Ravi, R., Sinha, A.: What about Wednesday? Approximation algorithms for multistage stochastic optimization. In: Chekuri, C., Jansen, K., Rolim, J.D.P., Trevisan, L. (eds.) APPROX 2005 and RANDOM 2005. LNCS, vol. 3624, pp. 86-98. Springer, Heidelberg (2005).

Digital Library

[18]

Immorlica, N., Karger, D., Minkoff, M., Mirrokni, V.S.: On the costs and benefits of procrastination: approximation algorithms for stochastic combinatorial optimization problems. In: Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 691-700 (2004).

Digital Library

[19]

Kakade, S.M., Kalai, A.T., Ligett, K.: Playing games with approximation algorithms. In: STOC 2007: Proceedings of the Thirty-Ninth Annual ACM Symposium on Theory of Computing, pp. 546-555. ACM, New York (2007).

Digital Library

[20]

Kalai, A., Vempala, S.: Efficient algorithms for on-line optimization. Journal of Computer and System Sciences 71, 291-307 (2005).

Digital Library

[21]

Katriel, I., Kenyon-Mathieu, C., Upfal, E.: Commitment under uncertainty: Two-stage stochastic matching problems. Theor. Comput. Sci. 408(2-3), 213-223 (2008).

Digital Library

[22]

Kelner, J.A., Nikolova, E.: On the hardness and smoothed complexity of quasiconcave minimization. In: Proceedings of the 48th Annual Symposium on Foundations of Computer Science, Providence, RI, USA (2007).

Digital Library

[23]

Kleinberg, J., Rabani, Y., Tardos, É.: Allocating bandwidth for bursty connections. SIAM Journal on Computing 30(1), 191-217 (2000).

Digital Library

[24]

Nie, Y(M.), Xing, W.: Shortest path problem considering on-time arrival probability. Transportation Research Part B: Methodological 43(6), 597-613 (2009).

[25]

Markowitz, H.M.: Mean-Variance Analysis in Portfolio Choice and Capital Markets. Basil Blackwell, Cambridge (1987).

[26]

Megiddo, N.: Combinatorial optimization with rational objective functions. Mathematics of Operations Research 4, 414-424 (1979).

Digital Library

[27]

Miller-Hooks, E., Mahmassani, H.: Path comparisons for a priori and time-adaptive decisions in stochastic, time-varying networks. European Journal of Operational Research 146(1), 67-82 (2003).

[28]

Nemirovski, A., Shapiro, A.: Convex approximations of chance constrained programs. SIAM Journal on Optimization 17(4), 969-996 (2006).

Digital Library

[29]

Nikolova, E., Kelner, J.A., Brand, M., Mitzenmacher, M.: Stochastic shortest paths via quasi-convex maximization. In: Azar, Y., Erlebach, T. (eds.) ESA 2006. LNCS, vol. 4168, pp. 552-563. Springer, Heidelberg (2006).

Digital Library

[30]

Onn, S.: Convex discrete optimization. Encyclopedia of Optimization, 513-550 (2009).

[31]

Papadimitriou, C.H., Yannakakis, M.: On the approximability of trade-offs and optimal access of web sources. In: Proceedings of the 41st Annual Symposium on Foundations of Computer Science, Washington, DC, USA, pp. 86-92 (2000).

Digital Library

[32]

Radzik, T.: Newton's method for fractional combinatorial optimization. In: Proceedings of the 33rd Annual Symposium on Foundations of Computer Science, pp. 659-669 (1992).

Digital Library

[33]

Rockafellar, R.T.: Coherent approaches to risk in optimization under uncertainty. In: Tutorials in Operations Research INFORMS, pp. 38-61 (2007).

[34]

Safer, H., Orlin, J.B., Dror, M.: Fully polynomial approximation in multicriteria combinatorial optimization. MIT Working Paper (February 2004).

[35]

Shmoys, D.B., Swamy, C.: An approximation scheme for stochastic linear programming and its application to stochastic integer programs. Journal of the ACM 53(6), 978-1012 (2006).

Digital Library

[36]

Sigal, C.E., Pritsker, A.A.B., Solberg, J.J.: The stochastic shortest route problem. Operations Research 28(5), 1122-1129 (1980).

[37]

Srinivasan, A.: Approximation algorithms for stochastic and risk-averse optimization. In: SODA 2007: Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, Philadelphia, PA, USA, pp. 1305-1313 (2007).

Digital Library

[38]

Swamy, C., Shmoys, D.B.: Approximation algorithms for 2-stage stochastic optimization problems. ACM SIGACT News 37(1), 33-46 (2006).

Digital Library

[39]

Warburton, A.: Approximation of pareto optima in multiple-objective, shortest-path problems. Oper. Res. 35(1), 70-79 (1987).

Digital Library

Cited By

Botea AKishimoto ANikolova EBraghin SBerlingerio MDaly E(2019)Computing multi-modal journey plans under uncertaintyJournal of Artificial Intelligence Research10.1613/jair.1.1142265:1(633-674)Online publication date: 1-May-2019
https://dl.acm.org/doi/10.1613/jair.1.11422
Korupolu MRajaraman R(2018)Robust and Probabilistic Failure-Aware PlacementACM Transactions on Parallel Computing10.1145/32103675:1(1-30)Online publication date: 21-Jun-2018
https://dl.acm.org/doi/10.1145/3210367
Staib MJegelka S(2017)Robust budget allocation via continuous submodular functionsProceedings of the 34th International Conference on Machine Learning - Volume 7010.5555/3305890.3306015(3230-3240)Online publication date: 6-Aug-2017
https://dl.acm.org/doi/10.5555/3305890.3306015
Show More Cited By

Approximation algorithms for reliable stochastic combinatorial optimization

Recommendations

Approximation Algorithms for Correlated Knapsacks and Non-martingale Bandits
FOCS '11: Proceedings of the 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science

In the stochastic knapsack problem, we are given a knapsack of size B, and a set of items whose sizes and rewards are drawn from a known probability distribution. To know the actual size and reward we have to schedule the item -- when it completes, we ...
Approximation Algorithms for Stochastic and Risk-Averse Optimization

We present improved approximation algorithms in stochastic optimization. We prove that the multistage stochastic versions of covering integer programs (such as set cover and vertex cover) admit essentially the same approximation algorithms as their standard (...
Improved Bounds in Stochastic Matching and Optimization

Real-world problems often have parameters that are uncertain during the optimization phase; stochastic optimization or stochastic programming is a key approach introduced by Beale and by Dantzig in the 1950s to address such uncertainty. Matching is a ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Guide Proceedings

APPROX/RANDOM'10: Proceedings of the 13th international conference on Approximation, and 14 the International conference on Randomization, and combinatorial optimization: algorithms and techniques

September 2010

781 pages

ISBN:3642153682

Editors:
Maria Serna
Universitat Politècnica de Catalunya, Dept. de Llenguatges i Sistemes Informàtics, Barcelona, Spain
,
Ronen Shaltiel
University of Haifa, Department of Computer Science, Haifa, Israel
,
Klaus Jansen
University of Kiel, Department of Computer Science, Kiel, Germany
,
José Rolim
University of Geneva, Centre Universitaire d'Informatique, Carouge, Switzerland

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 01 September 2010

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

15
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 12 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Botea AKishimoto ANikolova EBraghin SBerlingerio MDaly E(2019)Computing multi-modal journey plans under uncertaintyJournal of Artificial Intelligence Research10.1613/jair.1.1142265:1(633-674)Online publication date: 1-May-2019
https://dl.acm.org/doi/10.1613/jair.1.11422
Korupolu MRajaraman R(2018)Robust and Probabilistic Failure-Aware PlacementACM Transactions on Parallel Computing10.1145/32103675:1(1-30)Online publication date: 21-Jun-2018
https://dl.acm.org/doi/10.1145/3210367
Staib MJegelka S(2017)Robust budget allocation via continuous submodular functionsProceedings of the 34th International Conference on Machine Learning - Volume 7010.5555/3305890.3306015(3230-3240)Online publication date: 6-Aug-2017
https://dl.acm.org/doi/10.5555/3305890.3306015
Lauri MRopponen ARitala R(2017)Meeting a deadlineAnnals of Mathematics and Artificial Intelligence10.1007/s10472-016-9527-579:4(337-370)Online publication date: 1-Apr-2017
https://dl.acm.org/doi/10.1007/s10472-016-9527-5
Buchheim CKurtz J(2017)Min---max---min robust combinatorial optimizationMathematical Programming: Series A and B10.1007/s10107-016-1053-z163:1-2(1-23)Online publication date: 1-May-2017
https://dl.acm.org/doi/10.1007/s10107-016-1053-z
Jegelka SBilmes J(2017)Graph cuts with interacting edge weightsMathematical Programming: Series A and B10.1007/s10107-016-1038-y162:1-2(241-282)Online publication date: 1-Mar-2017
https://dl.acm.org/doi/10.1007/s10107-016-1038-y
Korupolu MRajaraman RScheideler CGilbert S(2016)Robust and Probabilistic Failure-Aware PlacementProceedings of the 28th ACM Symposium on Parallelism in Algorithms and Architectures10.1145/2935764.2935802(213-224)Online publication date: 11-Jul-2016
https://dl.acm.org/doi/10.1145/2935764.2935802
Piliouras GNikolova EShamma J(2016)Risk Sensitivity of Price of Anarchy under UncertaintyACM Transactions on Economics and Computation10.1145/29309565:1(1-27)Online publication date: 25-Oct-2016
https://dl.acm.org/doi/10.1145/2930956
Nikolova EStier-Moses NRoughgarden TFeldman MSchwarz M(2015)The Burden of Risk Aversion in Mean-Risk Selfish RoutingProceedings of the Sixteenth ACM Conference on Economics and Computation10.1145/2764468.2764485(489-506)Online publication date: 15-Jun-2015
https://dl.acm.org/doi/10.1145/2764468.2764485
Cominetti R(2015)Equilibrium routing under uncertaintyMathematical Programming: Series A and B10.1007/s10107-015-0889-y151:1(117-151)Online publication date: 1-Jun-2015
https://dl.acm.org/doi/10.1007/s10107-015-0889-y
Show More Cited By

View Options

View options

Media

Figures

Other

Tables

View Table of Contents