Oblivious Algorithms for Maximum Directed Cut: New Upper and Lower Bounds

Samuel Hwang, Noah G. Singer, Santhoshini Velusamy

In the maximum directed cut problem, the input is a directed graph $G=(V,E)$, and the goal is to pick a partition $V=S\cup (V\setminus S)$ of the vertices such that as many edg…