Two-stage Robust Network Design with Exponential Scenarios
Two-stage Robust Network Design with Exponential Scenarios
复制标题
具有指数场景的两阶段鲁棒网络设计
DOI：
10.1007/s00453-011-9596-0
复制
发表时间：
2008
期刊：
影响因子：
1.1
通讯作者：
M. Salavatipour
中科院分区：
文献类型：
--
作者：
R. Khandekar;G. Kortsarz;V. Mirrokni;M. Salavatipour
我们研究了在未指向的图表上的组合优化问题的两阶段，例如施泰纳树，施泰纳森林和无势力的设施位置。科学（FOCS'05），第367–378页，2005年），Golovin等。计算机科学的理论方面（Stacs），2006年）和Feige等人（第12国际整数编程和组合优化会议，第439-453、2007页）是两个阶段的计划问题在第1阶段做出一些决定之后，就必须以更高的成本完成解决方案，以满足强大的K-Steiner树问题。例如，一个人在第1阶段购买了一些边缘。然后在第2阶段揭示了K端子，并且必须以更高的成本购买更多的边缘，以完成1阶段的解决方案，以在这些终端上建造一条施泰纳树。最小化最坏情况下的总成本。在本文中，我们集中于指定的许多情况下，一个场景由k端子的任何子集（对于K-Steiner Tree）组成，或K终端对（用于K-Steiner森林）或任何K客户的子集（用于设施的位置）。为一个基于LP的通用框架，用于两个阶段鲁棒问题的近似算法可用于健壮的设施位置问题，但仅给出对数近似。我们介绍了强大的K-Steiner树（具有指数数量的场景）和鲁棒的无能力的设施位置问题组合，基于猜测最佳的成本和聚类，以靠近顶点。第2阶段（也称为通货膨胀），我们呈现一个恒定的近似值。第46届IEEE计算机科学基础的IEEE研讨会（FOCS'05），第367-378、2005页）和（Golovin等人在第23届计算机理论方面的年度研讨会上科学（Stacs），2006年）。
We study two-stage robust variants of combinatorial optimization problems on undirected graphs, like Steiner tree, Steiner forest, and uncapacitated facility location. Robust optimization problems, previously studied by Dhamdhere et al. (Proc. of 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS’05), pp. 367–378, 2005), Golovin et al. (Proc. of the 23rd Annual Symposium on Theoretical Aspects of Computer Science (STACS), 2006), and Feige et al. (Proc. of the 12th International Integer Programming and Combinatorial Optimization Conference, pp. 439–453, 2007), are two-stage planning problems in which the requirements are revealed after some decisions are taken in Stage 1. One has to then complete the solution, at a higher cost, to meet the given requirements. In the robust k-Steiner tree problem, for example, one buys some edges in Stage 1. Then k terminals are revealed in Stage 2 and one has to buy more edges, at a higher cost, to complete the Stage 1 solution to build a Steiner tree on these terminals. The objective is to minimize the total cost under the worst-case scenario.In this paper, we focus on the case of exponentially many scenarios given implicitly. A scenario consists of any subset of k terminals (for k-Steiner tree), or any subset of k terminal-pairs (for k-Steiner forest), or any subset of k clients (for facility location). Feige et al. (Proc. of the 12th International Integer Programming and Combinatorial Optimization Conference, pp. 439–453, 2007) give an LP-based general framework for approximation algorithms for a class of two stage robust problems. Their framework cannot be used for network design problems like k-Steiner tree (see later elaboration). Their framework can be used for the robust facility location problem, but gives only a logarithmic approximation.We present the first constant-factor approximation algorithms for the robust k-Steiner tree (with exponential number of scenarios) and robust uncapacitated facility location problems. Our algorithms are combinatorial and are based on guessing the optimum cost and clustering to aggregate nearby vertices. For the robust k-Steiner forest problem on trees and with uniform multiplicative increase factor for Stage 2 (also known as inflation), we present a constant approximation. We show APX-hardness of the robust min-cut problem (even with singleton-set scenarios), resolving an open question of (Dhamdhere et al. in Proc. of 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS’05), pp. 367–378, 2005) and (Golovin et al. in Proc. of the 23rd Annual Symposium on Theoretical Aspects of Computer Science (STACS), 2006).