Title: A gradient-based randomised heuristic for the maximum cut problem
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.
DOI: 10.1504/IJMOR.2012.046688
International Journal of Mathematics in Operational Research, 2012 Vol.4 No.3, pp.276 - 293
Published online: 23 Dec 2014 *
Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article