Approximating the Generalized Minimum Manhattan Network Problem
Approximating the Generalized Minimum Manhattan Network Problem
复制标题
近似广义最小曼哈顿网络问题
DOI：
10.1007/s00453-017-0298-0
复制
发表时间：
2013
期刊：
影响因子：
1.1
通讯作者：
A. Wolff
中科院分区：
文献类型：
--
作者：
Aparna Das;Krzysztof Fleszar;S. Kobourov;J. Spoerhase;S. Veeramoni;A. Wolff
考虑广义最小曼哈顿网络问题（GMMN）。这个问题的输入是一个setRofnpairs的终端，它们是点。目标是找到一个最小长度的直线网络，将每一对在曼哈顿路径上连接起来，即一条由轴线平行线段组成的路径，其总长度等于这对在曼哈顿的距离。这个问题是广泛研究的最小曼哈顿网络问题（MMN）的自然推广，其中MMN由所有可能的终端对组成。另一个重要的特例是众所周知的线性斯坦纳树突问题（RSA）。作为这些问题的推广，GMMN是np困难的。对于一般GMMN，目前还没有已知的近似算法。我们得到了GMMN的一种近似算法。我们的解决方案是基于刺入技术，一种解决曼哈顿网络问题的新方法。我们的算法的某些部分推广到高维，对任意固定维的问题给出了一个简单的近似算法。作为推论，我们在先前MMN尺寸的最佳比例（ESA 2011）上获得了指数级的改进。在此过程中，我们证明了2D-RSA的现有近似算法可以推广到更高的维度。
We consider thegeneralized minimum Manhattan network problem(GMMN). The input to this problem is a setRofnpairs of terminals, which are points in. The goal is to find a minimum-length rectilinear network that connects every pair inRby aManhattan path, that is, a path of axis-parallel line segments whose total length equals the pair’s Manhattan distance. This problem is a natural generalization of the extensively studiedminimum Manhattan network problem(MMN) in whichRconsists of all possible pairs of terminals. Another important special case is the well-knownrectilinear Steiner arborescence problem(RSA). As a generalization of these problems, GMMN is NP-hard. No approximation algorithms are known for general GMMN. We obtain an-approximation algorithm for GMMN. Our solution is based on a stabbing technique, a novel way of attacking Manhattan network problems. Some parts of our algorithm generalize to higher dimensions, yielding a simple-approximation algorithm for the problem in arbitrary fixed dimensiond. As a corollary, we obtain an exponential improvement upon the previously best-ratio for MMN inddimensions (ESA 2011). En route, we show that an existing-approximation algorithm for 2D-RSA generalizes to higher dimensions.