On Scenario Aggregation to Approximate Robust Optimization Problems
On Scenario Aggregation to Approximate Robust Optimization Problems
复制标题
关于近似鲁棒优化问题的场景聚合
DOI：
--
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
A. Chassein
中科院分区：
文献类型：
--
作者：
M. Goerigk;A. Chassein
由于大多数具有离散不确定性集的鲁棒组合极小-极大和极小-极大后悔问题都是NP-难问题，因此对近似算法和近似性界的研究是近年来的一个富有成果的领域。中点法是一个简单而著名的近似算法，它取所有场景的平均值，并解决名义型问题。尽管它的简单性，这种方法仍然给出了最好的知名的范围内的问题，如鲁棒最短路径，或鲁棒分配问题。在本文中，我们提出了一个简单的扩展的中点方法的基础上的场景聚合，它提高了目前的最佳K-近似结果的（eK）-近似任何期望的e>0。我们的方法可以应用到最小-最大以及最小-最大后悔问题。
As most robust combinatorial min-max and min-max regret problems with discrete uncertainty sets are NP-hard, research into approximation algorithm and approximability bounds has been a fruitful area of recent work. A simple and well-known approximation algorithm is the midpoint method, where one takes the average over all scenarios, and solves a problem of nominal type. Despite its simplicity, this method still gives the best-known bound on a wide range of problems, such as robust shortest path, or robust assignment problems. In this paper we present a simple extension of the midpoint method based on scenario aggregation, which improves the current best K-approximation result to an (eK)-approximation for any desired e>0. Our method can be applied to min-max as well as min-max regret problems.