COMPUTER SCIENCE COLLOQUIUM

Preprocessing with Guarantee

Saket Saurabh Institute of Mathematical Sciences C I T CAMPUS, TARAMANI, CHENNAI India

Wednesday, 18 April, 2012 at 15:15 IMADA's Seminar Room

ABSTRACT

Data reduction techniques are widely applied to deal with computationally hard problems in real world applications.

It has been a long-standing challenge to formally express the efficiency and accuracy of these ``pre-processing'' procedures. The framework of parameterized complexity turns out to be particularly suitable for a mathematical analysis of pre-processing heuristics. A kernelization algorithm is a pre-processing algorithm which simplifies the instances given as input in polynomial time, and the extent of simplification desired is quantified with the help of the additional parameter.

In this talk we will give an overview of some of the early work in the area and also survey newer techniques that have emerged in the design and analysis of kernelization algorithms.   The talk will also include a short portal into parameterized algorithms.

Host: Jørgen Bang-Jensen

---

SDU HOME | IMADA HOME | Previous Page

---

Daniel Merkle