direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Sie sind hier

TU Berlin

Page Content

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.

Zusatzinformationen / Extras