Title

Submitted final version of article “Hardness of Precedence Constrained Scheduling on Identical Machines” to appear in Siam Journal on Computing.

Attended workshop “Aspects of Coding Theory”, July 25-29 2011

Attended workshop on discrete optimization in the math department organized by Prof. Friedrich Eisenbrand. Participated by giving a talk on TSP but also discusssed several problems with visitors including Neal Young and Ricco Zenklausen that are both postdocs at MIT.

Submitted final version of article “On the Approximability of Single Machine Scheduling with Precedence Constraints” to apper in Mathematics of Operations Research (joint work with Christoph Ambuhl, Monaldo Mastrolilli and Nikos Mutsanas).

Started to work on caching with Yuval Cassuto. My contribution was to help developing a dynamic program for an abstract model of the problem. Yuval then implemented and verified the approach on real world data.

Attended operations research conference OR 2011 in Zurich where I gave a talk on TSP and served as a session chair.

Submitted final version of article “Hardness of Approximating Flow and Job Shop Scheduling Problems” to appear in Journal of the ACM (joint work with Monaldo Mastrolilli).

Worked on a revision of our paper “Approximating Linear Threshold Predicates” submitted to Transactions on Computation Theory (joint work with Mahdi Cheraghchi, Johan Hastad and Marcus Isaksson)

Helped organize and attended the workshop “Algebraic Coding Theory”, September 7-9 2011.

Attend a reading group consisting of the algo group where we try to understand how to use spatially coupled codes in order to increase the threshold where belief propagation works.

Started to work on the Single Source Rent or Buy problem with the discrete math group. This problem has many other famous problems as special cases, such as Steiner tree, finding a spanning tree with maximum number of leaves, etc. Our understanding of its approximability remains unsatisfying.

Served on the program committee of “The 18th Computing: the Australasian Theory Symposium (CATS) 2012.”

Attended FOCS and our paper “Approximating Graphic TSP by Matchings” received the best paper award.

I gave an invited talk at the ARC colloquium at Georgia Tech.

Submitted a journal version of the paper “Santa Claus Schedules Jobs on Unrelated Machines” that was invited to the special issue of Siam Journal on Computing based on STOC'11 papers.

I gave a plenary talk on the TSP problem at a workshop devoted to approximation algorithms at the Banff International Research Station.

Gave Two lectures at the undergraduate course “Algorithmique”.

Submitted final version of our paper “Approximating Linear Threshold Predicates” accepted to Transactions on Computation Theory (joint work with Mahdi Cheraghchi, Johan Hastad and Marcus Isaksson)

Worked on TSP with Tobias Moemke at KTH. We proved a tight analysis for half integral solutions of graph-TSP. This is an interesting but minor result that will be included in the journal version of our FOCS'11 paper on TSP.

Worked on asymmetric TSP with Nikhil Bansal and Jaroslaw Byrka. We tried to investigate some ideas that we had during the workshop at Banff but sofar without any success.

Read up on the Lasserre Hierarchy motivated by presentations and recent results at Banff. Together with Thomas Rothvoss and Per Austrin that I met at Banff, we try to use these techniques for fundamental scheduling problems. We can prove that many if not all previous results follow from the Lasserre Hierarchy but we are still researching for novel and better results obtained by this method.

Aleksandar Markovic finished his Bachelor project on the symmetric TSP that I supervised. He received the best grade.

Continued a previous work on the problem of finding a fair allocation of resources to players (Max-Min Fair Allocation Problem or Santa Claus Problem). Together with Lukas Polacek at KTH we prove that one can find a 1/4 approximate solution in quasi-polynomial time improving on the previously known exponential time algorithm.

Finalized the write up and submitted a conference version on our work on the Max-Min Fair Allocation problem.

Submitted final version of our journal paper “Tight Approximation Algorithms for Scheduling with Fixed Jobs and Non-Availability” (with Florian Diedrich, Klaus Jansen, and Lars Pradel) accepted to ACM Transactions on Algorithms.

Started to supervise a Master thesis by Monica Perrenoud on the Lasserre Hierarchy.

Gave invited interview talks for tenure-track assistant professorships at Stanford and EPFL.

Researched on hardness results for various vertex deletion problems such as the feedback vertex set (FVS) problem. Obtained simplified hardness proofs for FVS using the so called “It ain't over till it's over” theorem in the analysis of booelan functions. Moreover, the techniques lead to very structured results useful for obtaining stronger results for other problems such as other vertex deletion problems and project scheduling. Started to write up these results.

Gave invited interview talk for tenure-track assistant professorship at UCLA.

Gave invited talks at Princeton and Cornell.