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.
An approximation algorithm for the maximum cut problem and its experimental analysis / A. Bertoni, P. Campadelli, G. Grossi. - In: DISCRETE APPLIED MATHEMATICS. - ISSN 0166-218X. - 110:1(2001), pp. 3-12. ((Intervento presentato al convegno Conference on Algorithms and Experiments (ALEX98) tenutosi a Trento nel 1998 [10.1016/S0166-218X(00)00299-7].
An approximation algorithm for the maximum cut problem and its experimental analysis
A. Bertoni;P. Campadelli;G. Grossi
2001
Abstract
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.
Pubblicazioni consigliate
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
