0
$\begingroup$

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.

  1. 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?
  2. 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.

Improve this question
$\endgroup$
4
  • $\begingroup$ The abstract says it's an approximation algorithm -- a heuristic that guarantees that its output is "not too bad", where the allowed "badness" of each approximation (to an MST, and to a shortest path tree) is controlled by the user by setting the parameter $\gamma$. Of course, since there is not always an MST that is also a shortest path tree, if you want a tree that is a good approximation of one you may have to accept that it will be a bad approximation of the other. $\endgroup$
    – j_random_hacker
    May 24, 2018 at 13:15
  • $\begingroup$ I get that there is always a tradeoff between the two types of trees with this algorithm. Both trees will be suboptimal for their own cost. The article states it offers the best possible tradeoff between both trees for a given $\gamma$. I imagine it finds a (local) minimum for the combined cost functions using the 'shortcuts', but I can't follow how it relates to the optimal combined cost value. $\endgroup$
    – b9s
    May 24, 2018 at 14:10
  • $\begingroup$ I didn't see any "combined cost" mentioned in the abstract (is it described later?) -- just the two separate costs, with explicit bounds given in terms of $\gamma$. $\endgroup$
    – j_random_hacker
    May 24, 2018 at 14:15
  • $\begingroup$ It's not in the article, but it is relevant for my problem variant. I don't think the error bounds for both trees directly relate to it, which makes me wonder if an approximation bound can be derived for my variant based on the article. $\endgroup$
    – b9s
    May 24, 2018 at 14:23

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Browse other questions tagged or ask your own question.