I'm working on a problem that combines Steiner Trees and Shortest Path trees. We have a (sparse, connected) graph $G=(V,E)$ with non-negative edge weights and edge lengths, a set of terminals $T \subset V$ and a root node $s \in T$.
The goal is to connect all terminals to the root node while minimizing the total edge weight + the total lengths of the paths from each terminal to the root.
Minimizing just the edge weights gives the Steiner tree problem. Minimizing just the sum of path lenghts gives a shortest path problem.
Khuller, Samir, Balaji Raghavachari, and Neal Young. "Balancing minimum spanning trees and shortest-path trees." gives an algorithm for balancing this between MSTs and shortest path trees, but only considers the path from that node instead of the sum of incoming paths.
- I'm having trouble interpreting this article. Does the algorithm give a minimal cost solution for its own problem or is it a heuristic approximation?
- Can similar greedy strategies (expand from root to find shortcuts) also produce minimal cost solutions when balancing with Steiner trees (if you already have computed the Steiner tree)?
If (2) holds, then a custom solution for this cost function isn't required; you can compute the Steiner tree first, then minimize the path cost.