Approximation Algorithms for a Class of Stochastic Selection Problems with Reward and Cost Considerations

• 成果类型: Article
• 署名作者: Strinka, Zohar M. A.; Romeijn, H. Edwin
• 署名单位: University System of Georgia; Georgia Institute of Technology
• 刊物名称: OPERATIONS RESEARCH
• ISSN/ISSBN: 0030-364X
• DOI: 10.1287/opre.2017.1696
• 发表日期: 2018
• 页码: 834-848
• 关键词: MARKET SELECTION; RISK; decisions

摘要

We study a class of problems with both binary selection decisions and associated continuous choices that result in stochastic rewards and costs. The rewards are received based on the decision maker's selection, and the costs depend both on the decisions and realizations of the stochastic variables. We consider a family of risk-based objective functions that contains the traditional risk-neutral expected-value objective as a special case. A combination of rounding and sample average approximation is used to produce solutions that are guaranteed to be close to the optimal solution with high probability. We also provide an empirical comparison of the performance of the algorithms on a set of randomly generated instances of a supply cham example problem. The computational results illustrate the theoretical claims in the paper that, for this problem, high-quality solutions can be found with small computational effort.