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.
Complexity; Goemans and Williamson's algorithm; Local search; Optimization; Relaxation
Settore INF/01 - Informatica
1
Article (author)
File in questo prodotto:
Non ci sono file associati a questo prodotto.
Pubblicazioni consigliate

Caricamento pubblicazioni consigliate

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/2434/937928
Citazioni
  • ???jsp.display-item.citation.pmc??? 1
  • Scopus 10
  • ???jsp.display-item.citation.isi??? 6
social impact