[Solved]: Real world applications for Steiner Tree Problem?

Problem Detail: 

Are there real-world applications of the Steiner Tree Problem (STP)?

I understand that VSLI chip design is a good application of the STP. Are there any other examples of real world problems that people can suggest of that could be formulated in terms of the STP?

Background: I am beginning my PhD research and I am looking at using hybrid metaheuristics and primal-dual methods for the decomposition and solution of large-scale combinatorial optimisation problems. I find the STP fascinating, and I'm wondering if there is much real-world motivation for studying it, or if it is primarily of theoretical interest.

Asked By : guskenny83

Answered By : Thomas Bosman

I am currently writing my PhD proposal, which is about finding ways to apply theory from parameterized complexity, primarily tree decompositions, to realistic network optimization problems. But I mainly plan to work with Steiner Tree, not in the last place because its simple and there are a lot of papers/benchmarks available.

Stumbled on this question because I too have some trouble finding practical motivations for studying it. I think its practical relevance is more easily motivated by the enormous amount of optimization problems that are generalizations of the vanilla STP but are more flexible. There is a nice list here: http://theory.cs.uni-bonn.de/info5/steinerkompendium/netcompendium.pdf

I think some of the problems mentioned with phylogenetic trees can be directly formulated as STP but I haven't read the papers thoroughly.

This algorithm for connected facility location and single source rent-or-buy is also interesting: http://sma.epfl.ch/~eisenbra/Publications/jcss08cfl_final.pdf Though not directly modeled as an STP, solutions to these problems have a core that is a Steiner Tree and the algorithm makes use of a STP approximation algo directly to solve that part.

Also regarding heuristics for the STP you might be interested in this page: http://dimacs11.cs.princeton.edu/workshop.html There are quite a few new competitive algorithms that have been presented there.

---

Edit: You might also want to take a look at this book by William Cook:

In Pursuit of the Traveling Salesman

It is about the TSP, but that one is similarly theoretical. Chapter 3 contains really a load of concrete practical uses, not just the trivial tour finding stuff, but unexpected problems that can be solved by solving a TSP, including some biology problems as I mentioned. Part of the reason of the applicability seems to be the fact that there is a very powerful and accessible TSP solver out there, making it convenient to rephrase design problems as TSP's. I found it really inspiring as the same type of applications could be found for the STP I think (but there is no 'industry standard' solver for it so it doesn't happen in reality). Some of the chapter is free on Google books, though I recommend getting you hands on the full version cause some of the best examples are left out.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/42499