Maximizing Expected Utility for Stochastic Combinatorial Optimization Problems

References

• Akmann H, Newman A, Röglin H, Vöcking B (2007) Decision making based on approximate and smoothed Pareto curves. Theory Comput. Sci. 378(3):253–270.Crossref, Google Scholar
• Agrawal S, Saberi A, Ye Y (2008) Stochastic Combinatorial Optimization under Probabilistic Constraints. Arxiv preprint arXiv:0809.0460.Google Scholar
• Alimov S, Ashurov R, Pulatov A (1992) Multiple Fourier series and Fourier integrals, in commutative harmonic analysis. IV: Harmonic analysis in ℝn. Encyclopedia Math. Sci. 42:1–95.Crossref, Google Scholar
• Bansal N, Gupta A, Li J, Mestre J, Nagarajan V, Rudra A (2010) When LP is the cure for your matching woes: Improved bounds for stochastic matchings. Algorithmica 63(4):733–762.Crossref, Google Scholar
• Barahona F, Pulleyblank W (1987) Exact arborescences, matchings and cycles. Discrete Appl. Math. 16(2):91–99.Crossref, Google Scholar
• Bard J, Bennett J (1991) Arc reduction and path preference in stochastic acyclic networks. Management Sci. 37(2):198–215.Link, Google Scholar
• Bernoulli D (1954) Exposition of a new theory on the measurement of risk. Econometrica: J. Econometric Soc. 22(1):23–36. [Originally published in 1738, translated by Dr. Louise Sommer.]Crossref, Google Scholar
• Beylkin G, Monzón L (2002) On generalized Gaussian quadratures for exponentials and their applications. Appl. Computational Harmonic Anal. 12(3):332–373.Crossref, Google Scholar
• Beylkin G, Monzón L (2005) On approximation of functions by exponential sums. Appl. Computational Harmonic Anal. 19(1):17–48.Crossref, Google Scholar
• Beylkin G, Monzón L (2010) Approximation by exponential sums revisited. Appl. Computational Harmonic Anal. 28(2):131–149.Crossref, Google Scholar
• Bhalgat A (2011) Personal communication, January 20.Google Scholar
• Bhalgat A, Khanna S (2014) A utility equivalence theorem for concave functions. Integer Programming and Combinatorial Optimization (Springer, Berlin, Heidelberg), 126–137.Crossref, Google Scholar
• Bhalgat A, Goel A, Khanna S (2011) Improved approximation results for stochastic knapsack problems. ACM-SIAM Sympos. Discrete Algorithms (SIAM, Philadelphia, PA), 1647–1665.Google Scholar
• Carraway R, Schmidt R, Weatherford L (1993) An algorithm for maximizing target achievement in the stochastic knapsack problem with normal returns. Naval Res. Logist. 40(2):161–173.Crossref, Google Scholar
• Chekuri C, Khanna S (2000) A PTAS for the multiple knapsack problem. ACM-SIAM Sympos. Discrete Algorithms (SIAM, Philadelphia, PA), 213–222.Google Scholar
• Chen N, Immorlica N, Karlin A, Mahdian M, Rudra A (2009) Approximating matches made in heaven. International Colloquium on Automata, Languages and Programming (Springer, Berlin, Heidelberg), 266–278.Crossref, Google Scholar
• Cheney W, Light W (2000) A Course in Approximation Theory (Brook/Cole Publishing Company, Ann Arbor, MI).Google Scholar
• Cheng R, Chen J, Xie X (2008) Cleaning uncertain data with quality guarantees. Proc. VLDB Endowment 1(1):722–735.Crossref, Google Scholar
• Daskalakis C, De A, Diakonikolas I, Moitra A, Servedio RA (2014) A polynomial-time approximation scheme for fault-tolerant distributed storage. SODA (SIAM), 628–644.Google Scholar
• Dean B, Goemans M, Vondrák J (2005) Adaptivity and approximation for stochastic packing problems. ACM-SIAM Sympos. Discrete Algorithms (SIAM, Philadelphia, PA), 395–404.Google Scholar
• Dean B, Goemans M, Vondrak J (2008) Approximating the stochastic knapsack problem: The benefit of adaptivity. Math. Oper. Res. 33(4):945–964.Link, Google Scholar
• Fazel M, Chiang M (2005) Network utility maximization with nonconcave utilities using sum-of-squares method. Decision and Control, 2005 and 2005 Eur. Control Conf. CDC-ECC’05. 44th IEEE Conf. (IEEE), 1867–1874.Google Scholar
• Fishburn P (1970) Utility Theory and Decision Making (John Wiley & Sons, Inc., New York).Crossref, Google Scholar
• Garey M, Johnson D (1979) Computers and Intractability: A Guide to the Theory of NP-Completeness (W.H. Freeman, San Francisco).Google Scholar
• Geetha S, Nair K (1993) On stochastic spanning tree problem. Networks 23(8):675–679.Crossref, Google Scholar
• Goel A, Indyk P (1999) Stochastic load balancing and related problems. Annual Sympos. Foundations Comput. Sci. 579.Crossref, Google Scholar
• Gottlieb D, Shu C (1997) On the Gibbs phenomenon and its resolution. SIAM Rev. 39(4):644–668.Crossref, Google Scholar
• Goyal V, Ravi R (2010) A PTAS for the chance-constrained knapsack problem with random item sizes. Oper. Res. Lett. 38(3):161–164.Crossref, Google Scholar
• Guha S, Munagala K (2012) Adaptive uncertainty resolution in Bayesian combinatorial optimization problems. ACM Trans. Algorithms 8(1):1–23.Crossref, Google Scholar
• Gupta A, Pál M, Ravi R, Sinha A (2004) Boosted sampling: Approximation algorithms for stochastic optimization. ACM Sympos. Theory Comput. (ACM), 417–426.Google Scholar
• Henig M (1990) Risk criteria in a stochastic knapsack problem. Oper. Res. 38(5):820–825.Link, Google Scholar
• Huang L, Li J (2015) Approximating the expected values for combinatorial optimization problems over stochastic points. Automata, Languages, and Programming (Springer-Verlag, Berlin), 910–921.Google Scholar
• Huang L, Li J, Phillips JM, Wang H (2016) ε-kernel coresets for stochastic points. Eur. Sympos. Algorithms (Springer, Berlin, Heidelberg), 1–18.Google Scholar
• Ishii H, Shiode S, Nishida Yoshikazu T (1981) Stochastic spanning tree problem. Discrete Appl. Math. 3(4):263–273.Crossref, Google Scholar
• Kahneman D, Tversky A (1979) Prospect theory: An analysis of decision under risk. Econometrica: J. Econometric Soc. 47(2):263–291.Crossref, Google Scholar
• Kariv O, Hakimi S (1979) An algorithmic approach to network location problems. II: The p-medians. SIAM J. Appl. Math. 37(3):539–560.Crossref, Google Scholar
• Kleinberg J, Rabani Y, Tardos É (2000) Allocating bandwidth for bursty connections. SIAM J. Comput. 30(1):191–217.Crossref, Google Scholar
• Li J, Deshpande A (2009) Consensus answers for queries over probabilistic databases. ACM SIGMOD-SIGACT-SIGART Sympos. Principles of Database Systems (ACM, New York), 259–268.Crossref, Google Scholar
• Li J, Deshpande A (2010) Ranking continuous probabilistic data sets. Proc. VLDB Endowment 3(1):638–649.Crossref, Google Scholar
• Li J, Shi T (2014) A fully polynomial-time approximation scheme for approximating a sum of random variables. Oper. Res. Lett. 42(3):197–202.Crossref, Google Scholar
• Li J, Yuan W (2013) Stochastic combinatorial optimization via Poisson approximation. ACM Sympos. Theory Comput. (ACM, New York), 259–268.Crossref, Google Scholar
• Li J, Saha B, Deshpande A (2009) A unified approach to ranking in probabilistic databases. Proc. VLDB Endowment 3(1):638–649.Google Scholar
• Loui R (1983) Optimal paths in graphs with stochastic or multidimensional weights. Comm. ACM 26(9):670–676.Crossref, Google Scholar
• Martin R (2004) The St. Petersburg Paradox. The Stanford Encyclopedia of Philosophy. http://plato.stanford.edu/archives/fall2004/entries/paradox-stpetersburg.Google Scholar
• Mittal S, Schulz A (2008) A general framework for designing approximation schemes for combinatorial optimization problems with many objectives combined into one. Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques, 179–192.Crossref, Google Scholar
• Munteanu A, Sohler C, Feldman D (2014) Smallest enclosing ball for probabilistic data. Proc. 30th Annual Sympos. Computational Geometry (ACM, New York), 214–224.Google Scholar
• Murthy I, Sarkar S (1997) Exact algorithms for the stochastic shortest path problem with a decreasing deadline utility function. Eur. J. Oper. Res. 103(1):209–229.Crossref, Google Scholar
• Murthy I, Sarkar S (1998) Stochastic shortest path problems with piecewise-linear concave utility functions. Management Sci. 44(11):125–136.Link, Google Scholar
• Nikolova E (2010) Approximation algorithms for reliable stochastic combinatorial optimization. Internat. Workshop on Approximation Algorithms for Combinatorial Optim. Problems, 338–351.Google Scholar
• Nikolova E, Brand M, Karger D (2006) Optimal route planning under uncertainty. Proc. Internat. Conf. Automated Planning and Scheduling (AAAI Press, Palo Alto, CA), 131–140.Google Scholar
• Nikolova E, Kelner J, Brand M, Mitzenmacher M (2006) Stochastic shortest paths via quasi-convex maximization. Eur. Sympos. Algorithms (Springer, Berlin, Heidelberg), 552–563.Google Scholar
• Oberhettinger F (1973) Fourier Transforms of Distributions and Their Inverses: A Collection of Tables (Academic Press, New York).Google Scholar
• Osborne MR, Smyth GK (1995) A modified prony algorithm for fitting sums of exponential functions. SIAM J. Scientific Comput. 16(1):119–138.Crossref, Google Scholar
• Papadimitriou C, Yannakakis M (2000) On the approximability of trade-offs and optimal access of Web sources. Annual Sympos. Foundations Comput. Sci. (IEEE, Piscataway, NJ), 86–92.Crossref, Google Scholar
• Powell MJD (1981) Approximation Theory and Methods (Cambridge University Press).Crossref, Google Scholar
• Ralston A, Rabinowitz R (2001) A First Course in Numerical Analysis (Dover Publications, New York).Google Scholar
• Safer H, Orlin JB, Dror M (2004) Fully polynomial approximation in multi-criteria combinatorial optimization. Working paper, Massachusetts Institute of Technology, Cambridge, MA.Google Scholar
• Samuelson PA (1977) St. Petersburg paradoxes: Defanged, dissected, and historically described. J. Econom. Literature 15(1):24–55.Google Scholar
• Shmoys D, Swamy C (2006) An approximation scheme for stochastic linear programming and its application to stochastic integer programs. J. ACM 53(6):1012.Crossref, Google Scholar
• Sigal C, Pritsker A, Solberg J (1980) The stochastic shortest route problem. Oper. Res. 28(5):1122–1129.Link, Google Scholar
• Stein E, Shakarchi R (2003) Fourier Analysis: An Introduction (Princeton University Press, Princeton, NJ).Google Scholar
• Swamy C (2010) Risk-averse stochastic optimization: Probabilistically-constrained models and algorithms for black-box distributions. ACM-SIAM Sympos. Discrete Algorithms (SIAM, Philadelphia, PA), 1627–1646.Google Scholar
• Swamy C, Shmoys D (2006) Approximation algorithms for 2-stage stochastic optimization problems. ACM SIGACT News 37(1):33–46.Crossref, Google Scholar
• Von Neumann J, Morgenstern O (1947) Theory of Games and Economic Behavior, 2nd ed. (Princeton University Press, Princeton, NJ).Google Scholar