$O(\log n)$-Approximation Algorithms for Bipartiteness Ratio

Tasuku Soma, Mingquan Ye, Yuichi Yoshida

We propose an $O(\log n)$-approximation algorithm for the bipartiteness ratio of undirected graphs introduced by Trevisan (SIAM Journal on Computing, vol. 41, no. 6, 2012), where $…