We apologize for a recent technical issue with our email system, which temporarily affected account activations. Accounts have now been activated. Authors may proceed with paper submissions. PhDFocusTM
CFP last date
20 November 2024
Call for Paper
December Edition
IJCA solicits high quality original research papers for the upcoming December edition of the journal. The last date of research paper submission is 20 November 2024

Submit your paper
Know more
The week's pick
Responsive image
Improved Shuffled Frog Leaping Algorithm with Self-Adaptive Shuffling for Fuzzy Logic PD+G Controller Optimization in Robotic Manipulators

Duc Hoang Nguyen
Random Articles
Reseach Article

An Efficient Approximation Algorithm for Max-Cut

by Abdullah Al-malaise Al-ghamdi, Pawan Kumar Patel, Kunal Gupta
journal cover thumbnail

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

@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 },
issue_date = { February 2013 },
volume = { 63 },
number = { 8 },
month = { February },
year = { 2013 },
issn = { 0975-8887 },
pages = { 5-9 },
numpages = {9},
url = { https://ijcaonline.org/archives/volume63/number8/10484-5234/ },
doi = { 10.5120/10484-5234 },
publisher = {Foundation of Computer Science (FCS), NY, USA},
address = {New York, USA}
}
%0 Journal Article
%1 2024-02-06T21:13:35.728012+05:30
%A Abdullah Al-malaise Al-ghamdi
%A Pawan Kumar Patel
%A Kunal Gupta
%T An Efficient Approximation Algorithm for Max-Cut
%J International Journal of Computer Applications
%@ 0975-8887
%V 63
%N 8
%P 5-9
%D 2013
%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
  1. H. Shen and H. Zhang, "Improving exact algorithms for max-2-sat," Annals of Mathematics and Artificial Intelligence, vol. 44, April 2004.
  2. "Study of lower bound functions for max-2-sat," American Asso¬ciation for Artificial Intelligence, April 2004.
  3. 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.
  4. S. Sahni and T. Gonzalez, "P-complete approximation problems," Journal of The ACM, pp. 555–565, 1976.
  5. 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.
  6. 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.
  7. M. Grtschel, L. Lovsz, and A. Schrijver, "The ellipsoid method and its consequences in combinatorial optimization," Combinatorica, pp. 169– 197, 1981.
Index Terms

Computer Science
Information Sciences

Keywords

Approximation algorithm Balancing factor in Max-Cut Graphs Partitioning

Powered by PhDFocusTM