Linear Programming Relaxations for Steiner Trees
|Room:||Mathematics & Computer Building (MC) 5158|
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.
200 University Avenue West
Waterloo, ON N2L 3G1