
Vietnam Journal of Mathematics 34:4(2006) 389395

On the Approximability of MaxCut

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 MAXCUT problem. It is known that MAXCUT 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 MAXCUT can be solved by a linear time
approximation algorithm with the ratio less than 1 + α(for
any α > 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.


Established
by Vietnam Academy of Science and Technology & Vietnam Mathematical
Society
Published
by Springer since January 2013

