Approximations for node-weighted Steiner tree in unit disk graphs

作者：Xu X; Wang Y; Du H; Wan P J^*; Zou F; Li X; Wu W

来源：Optimization Letters, 2010, 4(3): 405-416.

DOI：10.1007/s11590-010-0194-x

• Node-weighted Steiner tree
• Unit-disk graph
• Approximation algorithm

Given a node-weighted connected graph and a subset of terminals, the problem node-weighted Steiner tree (NWST) seeks a lightest tree connecting a given set of terminals in a node-weighted graph. While NWST in general graphs are as hard as Set Cover, NWST restricted to unit-disk graphs (UDGs) admits constant-approximations. Recently, Zou et al. (Lecture notes in computer science, vol 5165, COCOA, 2008, pp 278-285) showed that any mu-approximation algorithm for the classical edge-weighted Steiner tree problem can be used to produce 2.5 mu-approximation algorithm for NWST restricted to UDGs. With the best known approximation bound 1.55 for the classical Steiner tree problem, they obtained an approximation bound 3.875 for NWST restricted to UDGs. In this paper, we present three approximation algorithms for NWST restricted to UDGs, the k-Restricted Relative Greedy Algorithm whose approximation bound converges to 1 + ln 5 approximate to 2. 61 as k --> infinity, the 3-Restricted Greedy Algorithm with approximation bound 4 1/3, and the k-Restricted Variable Metric Algorithm whose approximation bound converges to 3.9334 as k --> infinity.

• 出版日期2010-8
• 单位兰州大学; 清华大学