An Almost Logarithmic Approximation for Cutwidth

In the cutwidth problem, aka minimum cut linear arrangement, we are given a graph G and the goal is to order the vertices in a line such that the maximum number of edges crossing any vertex v is minimized. Since the seminal work of Leighton and Rao, the best known LP-based approximation for the problem is O(log^2 n), based on recursively finding balanced separators (this directly improves to O(log^1.5n) if we use ARV to find the separators). In this talk, I will describe a log^{1+o(1)} n LP-based approximation for the problem.

Based on joint work with Dor Katzelnik and Roy Schwartz.