×

Approximations for node-weighted Steiner tree in unit disk graphs. (English) Zbl 1202.90267

Summary: 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, F. Zou et al. [in: Combinatorial optimization and applications. Second international conference, COCOA 2008, St. John’s, NL, Canada, August 21–24, 2008. Proceedings. Berlin: Springer. Lecture Notes in Computer Science 5165, 278–285 (2008; Zbl 1168.90635)] 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 \approx 2.61\) as \(k \rightarrow \infty \), the 3-restricted greedy algorithm with approximation bound \({4\frac{1}{3}}\), and the \(k\)-restricted variable metric algorithm whose approximation bound converges to 3.9334 as \(k \rightarrow \infty \).

MSC:

90C35 Programming involving graphs or networks

Citations:

Zbl 1168.90635
Full Text: DOI

References:

[1] Borchers A., Du D.-Z.: The k-Steiner ratio in graphs. SIAM J. Comput. 26(3), 857–869 (1997) · Zbl 0870.68109 · doi:10.1137/S0097539795281086
[2] Berman P., Ramaiyer V.: Improved approximations for the Steiner tree problem. J. Algorithms 17(3), 381–408 (1994) · Zbl 0820.68049 · doi:10.1006/jagm.1994.1041
[3] Gröpl C., Hougardy S., Nierhoff T., Prömel H.J.: Approximation algorithms for the Steiner tree problem in graphs. In: Cheng, X., Du, D.-Z. (eds) Steiner trees in Industry, pp. 235–279. Kluwer, Dordrecht (2001)
[4] Guha S., Khuller S.: Improved methods for approximating node weighted Steiner trees and connected dominating sets. Inf. Comput. 150(1), 57–74 (1999) · doi:10.1006/inco.1998.2754
[5] Klein P., Ravi R.: A nearly best-possible approximation algorithm for node-weighted Steiner trees. J. Algorithms 19(1), 104–115 (1995) · Zbl 0836.68046 · doi:10.1006/jagm.1995.1029
[6] Papadimitriou C.H., Vazirani U.V.: On two geometric problems relating to the traveling salesman problem. J. Algorithms 5, 231–246 (1984) · Zbl 0551.90093 · doi:10.1016/0196-6774(84)90029-4
[7] Robins G., Zelikovsky A.: Tighter bounds for graph Steiner tree approximation. SIAM J. Discrete Math. 19(1), 122–134 (2005) · Zbl 1082.05088 · doi:10.1137/S0895480101393155
[8] Wan, P.-J., Du, D.-Z., Pardalos, P., Wu, W.: Greedy approximations for minimum submodular cover with submodular cost. Comput. Optim. Appl. (2009) (to appear) · Zbl 1188.90223
[9] Zelikovsky A.: The 11/6-approximation algorithm for the Steiner problem on networks. Algorithmica 9, 463–470 (1993) · Zbl 0768.68192 · doi:10.1007/BF01187035
[10] Zelikovsky, A.: Better approximation bounds for the network and Euclidean Steiner tree problems. Technical Report CS-96-06, Department of Computer Science, University of Virginia (1996)
[11] Zou, F., Li, X., Kim, D., Wu, W.: Two Constant Approximation Algorithms for Node-Weighted Steiner tree in Unit Disk Graphs. Lecture Notes in Computer Science, vol. 5165, pp. 278–285. COCOA (2008) · Zbl 1168.90635
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.