TU Berlin

Research Group Algorithmics and Computational ComplexityTalk 25.04.2013


Page Content

to Navigation

An LP relaxation for the Steiner Forest Problem

Anh Quyen Vuong, M.Sc. (TU Berlin)

In my talk, I will present parts of my Master's thesis about an LP relaxation for the Steiner Forest Problem (SFP),
which is called Lifted-Cut relaxation.
It will be shown that the Lifted-Cut Relaxation is better than the standard LP relaxation for SFP which is based on cut constraints.
The rest of my talk is about how to generalize Lifted-cut Relaxation to other problems in graphs.
For the Steiner Tree problem, we get a positive result: an LP relaxation with a polynomial number of constraints.
For the Network Design Problem, we will show a negative result by constructing a counter example.

25.04.2013 16:15
Anh Quyen Vuong
TEL 512

Back to the research colloquium site.


Quick Access

Schnellnavigation zur Seite über Nummerneingabe