|
|
|
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 + α(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
|
|
