Approximation Algorithms for Stochastic Combinatorial Optimization Problems
Approximation Algorithms for Stochastic Combinatorial Optimization Problems
复制标题
DOI：
10.1007/s40305-015-0116-9
复制
发表时间：
2016-03-01
影响因子：
1.4
通讯作者：
Liu, Yu
中科院分区：
文献类型：
--
作者：
Li, Jian;Liu, Yu
随机优化已成为处理各种优化问题中不确定性的主要方法，它通过对可能实现的概率分布进行建模来确定不确定性。传统上，随机优化研究的重点是各种随机数学规划（如线性规划、凸规划）。近年来，理论计算机科学界对随机组合优化问题产生了浓厚的兴趣。在这篇文章中，我们综述了一些关于经典组合优化问题的各种随机版本的最新结果。由于该领域的大多数问题都是NP-hard（或#P-hard，甚至PSPACE-hard），因此我们将重点放在提供具有可证明近似保证的多项式时间近似算法的结果上。我们围绕随机背包、随机匹配、多臂强盗等几个有代表性的问题进行了讨论。通过这些例子，我们介绍了几种流行的随机模型，如固定集模型、两阶段随机优化模型、随机自适应探测模型等，以及一些设计随机组合优化问题近似算法的有用技术，包括线性规划松弛法、增强采样、内容解析方案、泊松近似等。我们还提供了一些开放的研究问题。我们的目的是让读者快速了解该领域的模型、问题和技术，并希望能激发新的贡献
Stochastic optimization has established itself as a major method to handle uncertainty in various optimization problems by modeling the uncertainty by a probability distribution over possible realizations. Traditionally, the main focus in stochastic optimization has been various stochastic mathematical programming (such as linear programming, convex programming). In recent years, there has been a surge of interest in stochastic combinatorial optimization problems from the theoretical computer science community. In this article, we survey some of the recent results on various stochastic versions of classical combinatorial optimization problems. Since most problems in this domain are NP-hard (or #P-hard, or even PSPACE-hard), we focus on the results which provide polynomial time approximation algorithms with provable approximation guarantees. Our discussions are centered around a few representative problems, such as stochastic knapsack, stochastic matching, multi-armed bandit etc. We use these examples to introduce several popular stochastic models, such as the fixed-set model, 2-stage stochastic optimization model, stochastic adaptive probing model etc, as well as some useful techniques for designing approximation algorithms for stochastic combinatorial optimization problems, including the linear programming relaxation approach, boosted sampling, content resolution schemes, Poisson approximation etc. We also provide some open research questions along the way. Our purpose is to provide readers a quick glimpse to the models, problems, and techniques in this area, and hopefully inspire new contributions