On a Network Design Problem That Is Intractable on Trees

In this paper we study an optimization problem that arises in the design of communication networks. We show that this problem is NP-hard even when restricted to trees, and present several approximation results. In particular, we show that an integer programming formulation of the problem yields bounded ratio estimates for instances of the problem defined on trees.