A Faster Algorithm for Max Cut in Dense Graphs

Arijit Ghosh, Gopinath Mishra, Rahul Raychaudhury +1

We design an algorithm for approximating the size of \emph{Max Cut} in dense graphs. Given a proximity parameter $\epsilon \in (0,1)$, our algorithm approximates the size of \em…