The week's pick
Reseach Article
An Efficient Approximation Algorithm for Max-Cut
| International Journal of Computer Applications |
| Foundation of Computer Science (FCS), NY, USA |
| Volume 63 - Number 8 |
| Year of Publication: 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
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