Network Design via Core Detouring for Problems without a Core
Network Design via Core Detouring for Problems without a Core
复制标题
DOI：
10.1007/978-3-642-14165-2_42
复制
发表时间：
2010-07
期刊：
影响因子：
--
通讯作者：
F. Grandoni;T. Rothvoss
中科院分区：
文献类型：
--
作者：
F. Grandoni;T. Rothvoss
目前最著名的一些网络设计近似算法是基于随机抽样的。这种算法的关键步骤之一是将一组源节点连接到它们的随机子集。在最近的一项工作[Eisenbrand，Granoni，Rothvoç，Schäfer-Soda‘08]中，描述了一种新的技术，即核心绕行，以限制所提到的连接成本。这是通过定义次优连接方案来实现的，其中路径绕过适当的连通子图(核)。绕行路径的成本与堆芯的成本以及从源头到堆芯的距离的成本是有界的。对于连通设施选址、单水槽租赁或购买等问题，核心的选择是显而易见的(即最优解中的斯坦纳树)。其他更复杂的网络设计问题不会表现出这样的核心。在这篇文章中，我们证明了核心绕道仍然可以成功地应用。其基本思想是通过以适当的(不一定是微不足道的)方式操作最优解来构建一个方便的核心。我们通过对两个已被广泛研究的问题：虚拟专用网络设计和单宿批量购买问题提出了改进的近似算法来说明这一点。
Some of the currently best-known approximation algorithms for network design are based on random sampling. One of the key steps of such algorithms is connecting a set of source nodes to a random subset of them. In a recent work [Eisenbrand,Grandoni,Rothvoß,Schäfer-SODA’08], a new technique,core-detouring, is described to bound the mentioned connection cost. This is achieved by defining a sub-optimal connection scheme, where paths are detoured through a proper connected subgraph (core). The cost of the detoured paths is bounded against the cost of the core and of the distances from the sources to the core. The analysis then boils down to proving theexistenceof a convenient core.For some problems, such as connected facility location and single-sink rent-or-buy, the choice of the core is obvious (i.e., the Steiner tree in the optimum solution). Other, more complex network design problems do not exhibit any such core. In this paper we show that core-detouring can be nonetheless successfully applied. The basic idea is constructing a convenient core by manipulating the optimal solution in a proper (not necessarily trivial) way. We illustrate that by presenting improved approximation algorithms for two well-studied problems: virtual private network design and single-sink buy-at-bulk.