Yet another algorithm for dense max cut: go greedy.

Claire Mathieu, Warren Schudy

Browse the full SODA paper archive.