Home
Recent Issues
Volume 52	1	2	3	4
Volume 51	1	2	3	4
Volume 50	1	2	3	4
Volume 49	1	2	3	4
Volume 48	1	2	3	4
Past Issues
The Journal
Cover
Aims and Scope
Subscription Information
Editorial Board
Instructions for Author
Contact Us

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