International Journal of Computer Applications
Foundation of Computer Science (FCS), NY, USA
|
Volume 63 - Issue 8 |
Published: February 2013 |
Authors: Abdullah Al-Malaise Al-Ghamdi, Pawan Kumar Patel, Kunal Gupta |
![]() |
Abdullah Al-Malaise Al-Ghamdi, Pawan Kumar Patel, Kunal Gupta . An Efficient Approximation Algorithm for Max-Cut. International Journal of Computer Applications. 63, 8 (February 2013), 5-9. DOI=10.5120/10484-5234
@article{ 10.5120/10484-5234, author = { Abdullah Al-Malaise Al-Ghamdi,Pawan Kumar Patel,Kunal Gupta }, title = { An Efficient Approximation Algorithm for Max-Cut }, journal = { International Journal of Computer Applications }, year = { 2013 }, volume = { 63 }, number = { 8 }, pages = { 5-9 }, doi = { 10.5120/10484-5234 }, publisher = { Foundation of Computer Science (FCS), NY, USA } }
%0 Journal Article %D 2013 %A Abdullah Al-Malaise Al-Ghamdi %A Pawan Kumar Patel %A Kunal Gupta %T An Efficient Approximation Algorithm for Max-Cut%T %J International Journal of Computer Applications %V 63 %N 8 %P 5-9 %R 10.5120/10484-5234 %I Foundation of Computer Science (FCS), NY, USA
Significant research effort has been devoted in the study of approximation algorithms for NP-hard problems. Ap-proximation 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.