Description: Description: Description: Description: Description: Description: Description: Description: Description: Description: Description: Description: Description: Description: Description: Description: Description: Description: Description: Description: Description: Description: Description: VJM banner 

 

Home

 

Recent Issues

Volume 52

1

 

 

 

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