Authors: Walid Ben-Ameur; José Neto
Addresses: Institut Telecom, Telecom SudParis, CNRS-SAMOVAR UMR 5157, 9 rue Charles Fourier, 91011 Evry, France. ' Institut Telecom, Telecom SudParis, CNRS-SAMOVAR UMR 5157, 9 rue Charles Fourier, 91011 Evry, France
Abstract: In this paper we present a randomised heuristic for the maximum cut problem. It consists in finding an approximate solution of a formulation of the maximum cut problem as an unconstrained non-convex optimisation problem. Computational studies are reported. They indicate that the proposed method is competitive with the best known procedures present in the literature.
Keywords: combinatorial optimisation; randomised algorithms; maximum cut; gradient-based randomised heuristic.
International Journal of Mathematics in Operational Research, 2012 Vol.4 No.3, pp.276 - 293
Published online: 15 Apr 2012 *Full-text access for editors Access for subscribers Purchase this article Comment on this article