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: 15 Apr 2012 *

Full-text access for editors Access for subscribers Purchase this article Comment on this article