While visiting Aleksander Mądry at EPFL, I participated in the Algorithmic Meeting. This was the first time this event was organized and judging from the participants’ response,  not the last. The idea is to bring the european TCS community together and encourage more collaboration, joint research projects etc. The talks were supposed to be about plans for future research and open problems, rather than the typical conference style paper talks. I enjoyed the event and I think it served its purpose. One thing that was disappoing was the lack of chocolate filling in croissants served during coffee breaks. We collected a rather sizeable sample with Marcin Bieńkowski, and the results really leave no doubt. Hopefully, whoever organizes the next edition will take care of this small but important detail.

On a completely unrelated note (well, I guess it is a bit related since my Algorithmic Meeting talk was about it), my new paper on No-wait Flow Shop Scheduling, written together with Maxim Sviridenko, has just appeared on arxiv. I think the results are really nice, and the paper has something for everyone: metric embeddings (sort of), gadgets and plenty of epsilons. I will not give any more spoilers here, you can read more about it on our group’s blog.

This year has already been particularly busy in terms of travelling, and it is not going to stop any time soon. Currently I am staying at the University of Warwick, visiting Artur Czumaj, but also working with Matthias Englert, Maxim Sviridenko, and Nicolaos Matsakis. Having a great time, and some of the stuff we work on is very exciting, but I do not want to give away any more details until it is ready. I am staying here until December and then in February I am visiting Olek Mądry at EPFL Lausanne, and planning to also work with Ola Svensson and others. In the meantime, a double US feature consisting of SODA (to present the superstring paper) and ITCS (to present a new joint paper with Marek Cygan, Matthias Englert, Anupam Gupta and Piotr Sankowski, more details to come) is waiting for me early January. To get a little rest from all this travelling (you wish) I plan to do some skiing in Austria 🙂

Our Algorithms Group has just started a blog . The inaugural post celebrates a rather rare and happy event – four papers written by members of our group were accepted to FOCS 2012. Congratulations to the authors!

After 8 years of struggle I finally managed to make certain ideas work, and as a result, I have an algorithm that approximates the Shortest Superstring problem with a ratio (slightly) smaller than the long standing 2 1/2. The algorithm is surprisingly simple, since it chooses the best solution out of the following: (1) returned by one of the known 2 1/2 approximation algorithms (2) returned by a particularly naive cycle-breaking greedy algorithm. More details here.