Theory Seminar

An Almost Logarithmic Approximation for Cutwidth

Nikhil BansalUniversity of Michigan
3725 Beyster BuildingMap
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.


Greg Bodwin


Euiwoong Lee