[NotOscarWilde]

Elaine Levey, Thomas Rothvoss - A Lasserre-based (1+ε)-approximation for Pm∣pj=1,prec∣Cmax http://arxiv.org/abs/1509.07808

People are very excited about graph isomorphism being solvable in quasipolynomial time, but there are a few more problems from the seminal Garey, Johnson book that are still unknown to be in either P or NP-c or neither. One of them is computing the optimal schedule for three machines processing some tasks (jobs), when the tasks have all the same size, but there are dependencies among some of them and you have to do them in order.

This paper proves that there is a (1+ε)-approximation of this problem in "slightly more than quasipolynomial time" (I love this phrasing).

The technique they use is a Lasserre hierarchy which is a very exciting tool in theoretical computer science, although there still exist only a couple results where this hierarchy approach brings more to the table than other methods for designing efficient algorithms. This is one more to the list!