#### Theory Seminar

# An Almost Logarithmic Approximation for Cutwidth

Nikhil BansalUniversity of Michigan

WHERE:

3725 Beyster Building

WHEN:

Friday, April 12, 2024 @ 2:00 pm - 3:00 pm

This event is free and open to the publicAdd to Google Calendar

This event is free and open to the publicAdd to Google Calendar

WEB: Event Website

SHARE:

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.