|
Given a set $T$ of terminal vertices in an undirected weighted graph, the Steiner
tree problem is to find the cheapest tree containing $T$ using possibly some other
vertices of the graph.
This problem is a classical NP-hard combinatorial optimization problems, and we
are interested in designing efficient approximation algorithms. In particular, we
investigate the technique of designing LP relaxations of an IP for the problem and
studying their integrality gaps (the ratio of the value of the IP to the LP).
In this talk, I will survey the various relaxations that have been studied for the
problem, and point out their successes or the lack thereof in designing
approximation algorithms. We will talk about old, new and fresh off the oven
developments.
|