Research Article
An Efficient Approximation Algorithm for Max-Cut
|
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 |
10.5120/10484-5234
|
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
Abstract
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.
References
- H. Shen and H. Zhang, "Improving exact algorithms for max-2-sat," Annals of Mathematics and Artificial Intelligence, vol. 44, April 2004.
- "Study of lower bound functions for max-2-sat," American Asso¬ciation for Artificial Intelligence, April 2004.
- J. Gramm, E. A. Hirsch, R. Niedermeier, and P. Rossmanith, "New worst-case upper bounds for max-2-sat with application to max-cut," ECCC, 2000.
- S. Sahni and T. Gonzalez, "P-complete approximation problems," Journal of The ACM, pp. 555–565, 1976.
- M. X. Goemans and D. Williamson, "Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite program¬ming," Journal of the ACM, vol. 42, pp. 1115–1145, 1995.
- J. Alber, J. Gramm, and R. Niedermeier, "Faster exact algorithms for hard problems: A parameterized point of view," Discrete Mathematics, vol. 229, pp. 3–27, 2000.
- M. Grtschel, L. Lovsz, and A. Schrijver, "The ellipsoid method and its consequences in combinatorial optimization," Combinatorica, pp. 169– 197, 1981.
Index Terms
Keywords