Approximating Spanning Trees with Inner Nodes Cost

We consider the practical NP-complete problem of finding a minimum weight spanning tree with both edge weights and inner nodes weights. We present two polynomial time algorithms with approximation factors of 2.35 · ln n and 2Hn, respectively, where n is the number of nodes in the graph and Hn is the n-th Harmonic number. This nearly matches the lower bound of (l-in )Hn, for any in ge 0. We also give an approximation algorithm with approximation factor Delta - 1, where Delta is the maximum degree of the graph. For metric spaces, we give a 3.105-approximation algorithm and show that an approximation factor of 1.463 is impossible unless {NP subseteq DTIME[n^{O(log longn)} ]}.