Lorentz Center - WorKer 2010: Workshop on Kernelization from 8 Nov 2010 through 12 Nov 2010
  Current Workshop  |   Overview   Back  |   Home   |   Search   |     

    WorKer 2010: Workshop on Kernelization
    from 8 Nov 2010 through 12 Nov 2010


Scientific Report


An important step when solving combinatorially hard problems (from many applications) is to first preprocess the data, i.e., transform the input to a smaller sized but otherwise equivalent input, and use a slow exact solving method on the result. In this workshop, we look at a mathematical analysis of such preprocessing algorithms, termed kernelization algorithms.

The workshop program consisted of eleven keynote lectures, nine participant lectures, and two lectures in a special session on the multi-cut problem. In addition, several discussion sessions were held, discussing in depth in what direction standardization of the main used definition of kernelization should go, important open problems in the field, and the publicity of kernelization. Also, participants worked on open problems with other participants. The social program consisted of a cheese and wine party at the first day of the conference, and a very nice conference dinner during a boat trip in the neighborhood of Leiden.

The lectures presented the most important recent developments in kernelizations, including new techniques to obtain lower bounds for kernels, including the very new technique of cross composition, meta-results, i.e., techniques that allow to obtain kernelization algorithms for not one, but entire classes of problems (the notion of protrusion plays an important role here), kernelization for problems from logic and data clustering, the use of nonstandard parameters, and notions related to kernelization. The lectures were very informative, often explaining deep new results in a clear way, and gave a good view of the current state of research in the field.

In two special sessions, the participants discussed the definition of kernelization. These discussions were very lively. A report on the conclusions of the discussion is in preparation.

Over fifty participants from many different countries and continents gathered for the workshop. Most of the world experts from the field came to the workshop. We expect that a number of new results and papers will be the results of the work that was carried out or started during the workshop. The excellent facilities and the helpful staff were very beneficial to make the workshop a big success.