Dagstuhl - Monday afternoon

The theme of the afternoon: FPT-type algorithms.

Daniel Marx gave a survey talk on FPT and approximation algorithms. Very interesting for me, because it is very close to my research area even though I have not been following what was happening. There are lots of results coming out, and some of them seem quite clever. Most of the results he mentioned were for optimization problems on graphs. Unfortunately there were almost no proofs, but the ingredients, according to his keywords, seems quite close to techniques for approximation schemes.

Why are FPT results interesting? One reason: because they seem to give some insight into the structure of those basic problems; at least, that's my impression, although, without an actual detailed proof, it's kind of hard to tell. Another reason: because they can conceivably lead to actual implementations. But Daniel was kind of vague about that; it's not the direction in which his personal interests are taking him, and I am maybe with the wrong crowd this week to get a good answer to that question. (One might also wonder: why do I, a pure theoretician, care?) Certainly, the area seems to be taking off these days.

Klaus Jansen and Ildi Schlotter both talked about the most famous bin packing/cutting stock problem: is there an approximation algorithm with additive approximation +1? Klaus talked about the special case where there are only a constant number k of distinct item sizes, and Ildi talked about the special case where there are only a constant number k of bins available, and their runtimes were of the form f(k)*poly(input size), where the polynomial was independent of k: in that sense, their algorithms were FPT-type. Because of the famous open problem driving research in that area, I did not need further motivation, so I was pretty interested in those results. After that I had had enough and skipped the last talk of the day.