Robust Combinatorial Optimization with Exponential Scenarios
Robust Combinatorial Optimization with Exponential Scenarios
复制标题
具有指数场景的鲁棒组合优化
DOI：
10.1007/978-3-540-72792-7_33
复制
发表时间：
2007
影响因子：
2.7
通讯作者：
V. Mirrokni
中科院分区：
文献类型：
--
作者：
U. Feige;K. Jain;Mohammad Mahdian;V. Mirrokni
遵循进行随机优化的两阶段优化框架[15,8]，我们研究了具有指数次数的场景数量的可靠两阶段优化问题的近似算法。在此工作之前，Dhamdhere等人。 [8]引入了针对两阶段强大优化问题的近似算法，并具有明确给定的方案。在本文中，我们假设一组可能的方案是隐性地给出的，例如，在活动客户端数量上的上限。在两阶段的强大优化中，我们需要在对手行动之前的第一阶段预购一些资源。在第二阶段，在对手选择需要覆盖的客户之后，我们需要以高昂的价格购买额外资源来补充解决方案。目标是在最坏的情况下最小化成本。我们提供了使用LP圆形解决此类问题的一般方法。我们的方法发现了强大的优化与在线竞争算法之间的有趣联系。我们使用这种方法以及已知的在线算法来开发近似算法，以解决多个可靠的覆盖问题，例如设置盖，顶点盖和边缘盖。我们还研究了一个简单的购买式购买，要么涵盖第一阶段的所有项目，要么在第一阶段什么都不做，并等待在第二阶段构建完整的解决方案。我们表明，该算法给出了这些涵盖问题的未加权变体的紧密近似因素，但对于一般的加权问题而言，其性能较差。
Following the well-studied two-stage optimization framework for stochastic optimization [15,8], we study approximation algorithms for robust two-stage optimization problems with an exponential number of scenarios. Prior to this work, Dhamdhere et al. [8] introduced approximation algorithms for two-stage robust optimization problems with explicitly given scenarios. In this paper, we assume the set of possible scenarios is given implicitly, for example by an upper bound on the number of active clients. In two-stage robust optimization, we need to pre-purchase some resources in the first stage before the adversary's action. In the second stage, after the adversary chooses the clients that need to be covered, we need to complement our solution by purchasing additional resources at an inflated price. The goal is to minimize the cost in the worst-case scenario. We give a general approach for solving such problems using LP rounding. Our approach uncovers an interesting connection between robust optimization and online competitive algorithms. We use this approach, together with known online algorithms, to develop approximation algorithms for several robust covering problems, such as set cover, vertex cover, and edge cover. We also study a simple buy-at-oncealgorithm that either covers all items in the first stage or does nothing in the first stage and waits to build the complete solution in the second stage. We show that this algorithm gives tight approximation factors for unweighted variants of these covering problems, but performs poorly for general weighted problems.