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

An approximation algorithm for the maximum cut problem is designed and analyzed; its performance is experimentally compared with that of a neural algorithm and that of Goemans and Williamsonʹs algorithm. Although the guaranteed quality of our algorithm in the worst-case analysis is poor, we give experimental evidence that its average behavior is better than that of Goemans and Williamsonʹs algorithm.