In the well-known Steiner Tree problem, the objective is to connect a set of terminals at the least total cost. We can further constrain the problem by specifying upper bounds for the distance of each terminal to a chosen root terminal. Further, using the Lagrangianr elaxation of this restriction, we can penalize large distances in the objective function rather than applying strict distance constraints. We arrive at a special case of the so-called Cost-Distance Steiner Tree Problem in which we have a single weight function on the edges.

In this talk, I will present several results from my master's thesis that concern the Cost-Distance Steiner Tree Problem. The NP-hardness of the Cost-Distance Steiner Tree Problem trivially follows from the fact that the regular Steiner Tree problem is the special case where we set demand weights (Lagrange multipliers) of the terminals to zero. I therefore proceed to prove that the problem remains NP-hard in three restricted cases that do not contain the regular Steiner Tree Problem as a special case. Then I improve on a previous constant-factor approximation for the single-weighted case by using a hybrid method of an approximate Steiner tree with a shortest-path tree replacing sections of the tree where path segments are used by many terminals with demand weights summing to higher than a tunable threshold. I also use a similar approach to extend Arora's dynamic-programming method for the two-dimensional geometric Steiner Tree Problem to the case with the penalizing terms in the objective function.