
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

