Recent Issues Volume 37 1 2 3 4 Volume 36 1 2 3 4 Volume 35 1 2 3 4 Volume 34 1 2 3 4 Volume 33 1 2 3 4 Past Issues The Journal Cover Aims and Scope Subscription Information Editorial Board Instructions for Author Contact Us Related Links

Vietnam Journal of Mathematics 34:4(2006) 389-395  On the Approximability of Max-Cut Le Cong Thanh Abstract.  We introduce the almost sure performance ratio of an approximation algorithm for a discrete optimization problem and consider it for the MAX-CUT problem. It is known that MAX-CUT cannot be solved by a polynomial time approximation algorithm with the ratio less than $1.0625$ for all instances of the problem unless $P = NP$. The aim of this note is to show that MAX-CUT can be solved by a linear time approximation algorithm with the ratio less than $1+ \varepsilon$ (for any $\varepsilon>0$) for almost every instance, and hence with the almost sure performance ratio $1$.   2000 Mathematics Subject Classification: 68Q17. Keywords: Approximation algorithm, absolute performance ratio, almost sure performance ratio.

Vietnam Academy of Science and Technology & Vietnamese Mathematical Society © Copyright 2009 Vietnam Journal of Mathematics. All rights reserved.