Approximation algorithms for geometric tour and network design problems (extended abstract)
Approximation algorithms for geometric tour and network design problems (extended abstract)
复制标题
几何游览和网络设计问题的近似算法（扩展摘要）
DOI：
--
复制
发表时间：
1995
期刊：
影响因子：
--
通讯作者：
Joseph S. B. Mitchell
中科院分区：
文献类型：
--
作者：
Cristian S. Mata;Joseph S. B. Mitchell
红蓝分离问题（RBSP）：考虑寻找最小周长乔丹曲线（必然是一个简单的多边形）的问题，该曲线将一组“红色”点R与一组“蓝色”点B分开。这个问题被认为是NP难的，使用欧几里德旅行推销员问题的简化[3，12]。（将TSP实例中的每个城市替换为一对点，一个红色和一个蓝色，非常接近。虽然欧几里得TSP可以近似为1.5倍最优的因子（使用Christofides的启发式[9]），但看似相关的RBSP已经挑战了以前设计可证明的良好近似算法的尝试。我们给出了RBSP的一个O（logm）近似界算法，其中m < n是最小边数
Red-Blue Separation Problem (RBSP): Consider the problem of finding a minimum-perimeter Jordan curve (necessarily, a simple polygon) that separates a set of “red” points, R, from a set of “blue” points, B. This problem is seen to be NP-hard, using a reduction from the Euclidean traveling salesman problem [3, 12]. (Replace each city in the TSP instance by a pair of points, one red and one blue, very close together.) While Euclidean TSP can be approximated to within a factor of 1.5 times optimal (using Christofides’ heuristic [9]), the seemingly related RBSP has defied previous attempts to devise a provably good approximation algorithm. We provide an O(log m) approximation bound algorithm for RBSP, where m < n is the minimum number of sides