An approximation algorithm for the maximum cut problem and its experimental analysis

An approximation algorithm for the maximum cut problem is designed and anal yzed; its performance is experimentally compared with that of a neural algo rithm and that of Goemans and Williamson's algorithm. Although the guarante ed quality of our algorithm in the worst-case analysis is poor, we give exp erimental evidence that its average behavior is better than that of Goemans and Williamson's algorithm. (C) 2001 Elsevier Science B.V. All rights rese rved.