TU Berlin

Research Group Algorithmics and Computational ComplexityTalk 20.12.2012

isti-logo

Page Content

to Navigation

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.

Date
Speaker
Location
Language
20.12.2012 16:15
Andreas Feldmann
TEL 512
german/english

Back to the research colloquium site.

Navigation

Quick Access

Schnellnavigation zur Seite über Nummerneingabe