|
The MAX-CUT problem MAX-CUT is the problem of computing the maximum cut of a graph G(V,E), i.e., that of partitioning the vertex set V into two parts so that the number of edges joining vertices in different parts is as large as possible. In [KKS_ESA06], Kaporis, Kirousis, and Stavropoulos give a deterministic polynomial-time algorithm which for any given average degree d and asymptotically almost all random graphs G in G(n, m= d n /2) outputs a cut of G whose ratio (in cardinality) with the maximum cut is at least 0.952. Authors have implemented a number of algorithms for computing the upper and lower bound of the maximum cut of input instances in G(n,m). Sources are available only for educational or research purposes.
Source code for computing the upper bound (via differential equations) The maple code MajorityCuts.mws on input a random graph of average degree 1<d<20, computes an upper bound to the typical value of the cut. The notes UB.pdf contain the combinatorial argument for computing the upper bound and are helpful for the understanding of the maple code.
Source code for computing the lower bound (via differential equation technique) lb-deq.c (c code for linux, solaris, and windows) Purpose: computes a lower bound to the typical size of the cut produced by algorithm A (see [KKS_ESA06]) of a random graph G by applying the differential equation technique. The output is directed to outfile. Compile: gcc -lm lb-deq.c -o lb-deq Syntax: lb-deq d step lbucket outfile d is the average degree of the graph Example: lb-deq 2.0 0.000005 0.00001 lb-deq.out Output: d= 2.0 cut=0.94561000 Example: lb-deq 4.0 0.0000005 0.000001 lb-deq.out d= 4.0 cut=0.82974400 lb-deq-batch.c (c code for linux, solaris, and windows) Purpose: computes a lower bound to the typical size of the cut produced by algorithm A (see [KKS_ESA06]) of a random graph G by applying the differential equation technique, for d=dl to d=du with step dstep. The output is directed to outfile. Compile: gcc -lm lb-deq-batch.c -o lb-deq-batch Syntax: lb-deq-batch dl du dstep step lbucket outfile Example: lb-deq-batch 2.0 2.5 0.1 0.000001 0.00001 lb-deq.out Output:
Source code for computing the lower bound (via simulation) lb-sim.c (c code for linux, solaris, and windows) Purpose: computes the size of the cut produced by algorithm A (see [KKS_ESA06]) of a random graph in G(n,m) with 2^k nodes and average degree d. The output is directed to outfile. Compile: gcc -lm lb-sim.c -o lb-sim Syntax: lb-sim k d outfile Example: lb-sim 15 4.0 lb-sim.out Output: n=32768 d= 4.0 cut=0.82994080 (Many thanks to Prof. Ioannis Caragiannis for his significant contribution to the implementation of the algorithm.) lb-sim-batch.c (c code for linux, solaris, and windows) Purpose: computes the size of the cut produced by algorithm A (see [KKS_ESA06]) of a random graph in G(n,m) with 2^k nodes and average degree d, for d=dl to d=du with step dstep. The output is directed to outfile. Compile: gcc -lm lb-sim-batch.c -o lb-sim-batch Syntax: lb-sim-batch k dl du dstep outfile Example: lb-sim-batch 17 2.0 2.5 0.1 lb-sim.out Output:
Page last updated on August 26, 2006. (c) A.C. Kaporis, L.M.Kirousis, and E.C. Stavropoulos |