An Efficient Approximation Algorithm for Max-Cut
Abdullah AL-MalaiseAL-Ghamdi, Pawan Kumar Patel, Kunal Gupta · International Journal of Computer Applications · 2013
Significant research effort has been devoted in the study of approximation algorithms for NP-hard problems.Approximation algorithm for Max-Cut problem with performance guarantee of 0.87856 is long known.In this work we study balanced Max-Cut problem.We give a balancing factor β for given α such that the approximate solution is at least 0.87856 times the optimal α-balanced cut and it is itself β-balanced.