  The Max-Cut problem is a well known combinatorial optimization problem. In
this paper we describe a fast approximation method. Given a graph G, we want to
find a cut whose size is maximal among all possible cuts. A cut is a partition
of the vertex set of G into two disjoint subsets. For an unweighted graph, the
size of the cut is the number of edges that have one vertex on either side of
the partition; we also consider a weighted version of the problem where each
edge contributes a nonnegative weight to the cut. We introduce the signless
Ginzburg-Landau functional and prove that this functional Gamma-converges to a
Max-Cut objective functional. We approximately minimize this functional using a
graph based signless Merriman-Bence-Osher scheme, which uses a signless
Laplacian. We show experimentally that on some classes of graphs the resulting
algorithm produces more accurate maximum cut approximations than the current
state-of-the-art approximation algorithm. One of our methods of minimizing the
functional results in an algorithm with a time complexity of O(|E|), where |E|
is the total number of edges on G.
