8
$\begingroup$

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.

$\endgroup$
4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thanks a lot for your input, that compendium of problems was particularly useful. $\endgroup$ – guskenny83 May 18 '15 at 17:24
  • $\begingroup$ @guskenny83 I added something I found later which might be interesting to you too $\endgroup$ – Thomas Bosman Jun 4 '15 at 16:35
  • $\begingroup$ thanks for that, i have been thinking about reading that book for a while now, i just never have got around to it.. $\endgroup$ – guskenny83 Jun 9 '15 at 7:03
1
$\begingroup$

My apologies up front for not having more detail on my comment here. But I too have considered an approach of using STP in solving routing information. In fact, there are already some applications in the polynomial space where least distant routing adds vertices to direct someone, say off of an inter-state highway to surface streets, to reach shorter distances routes (directions). They may not be faster based on speed or traffic conditions.

The calculations strictly considered distance. It was partially rejected as an application since the trucking industry was not able to utilize residential streets for example, or alleys, for routing. But biking, walking, hiking could. There does seem to be some inclusion of this in Google maps now as you can choose you mode of transportation and I believe, this allows for more refined points on a greater number of qualifying routes. For example, traveling on city bus, bike or by foot, would not normally route to the interstate.

There used to be some info in the Google API, older versions, covering this routing. Not sure if it is still there, this was about 3 years ago. Good Luck.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.