Inhalt des Dokuments
Novel Directions in Data Reduction for NP-Hard Problems: Truth-Table Kernelizations
Dr. Andreas Feldmann (University of Waterloo, Canada)
Recently there has been quite a development in understanding the Steiner Tree Problem using LPs. This started with the breakthrough paper of Byrka et al. (STOC 2010), who gave an iterative rounding approach achieving an ln(4)-approximation. However their approach is very slow (although polynomial) since they have to recompute the solution to a very large LP in each iteration after rounding. I will present a current paper by Goemans et al. (STOC 2012) who take a fresh look at the approach presented by Byrka et al. They show how to speed up the computation by updating the current solution to the LP after each iteration, which means they do not have to recompute the solutions from scratch. This is done by proving that the structure of necessary changes of the LP solution from one iteration to the next, forms a matroid.
Back to the research colloquium site.