TU Berlin

Research Group Algorithmics and Computational ComplexityTalk 20.12.2012



zur Navigation

Es gibt keine deutsche Übersetzung dieser Webseite.

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.

20.12.2012 16:15
Andreas Feldmann
TEL 512

Back to the research colloquium site.



Schnellnavigation zur Seite über Nummerneingabe