Una Benlic and Jin-Kao Hao. Breakout Local Search for Maximum Cut Problem. Engineering Applications of Artificial Intelligence 26(3): 1162-1173, 2013.


Improved solutions for 35 out of 71 instances from http://www.stanford.edu/~yyye/yyye/Gset/ for the maximum cut problem. The new improved results is given in parentheses.

G25(13340) • G26(13328) • G27(3341) • G28(3298) • G29(3405) • G30(3413) • G31(3309) • G36(7678) • G38(7687) • G39(2408) • G40(2400) • G41(2405) • G42(2481) • G47(6657) • G51(3848) • G52(3851) • G53(3850) • G54(3852) • G55(10294) • G56(4012) • G57(3492) • G58(19263) • G59(6078) • G60(14176) • G61(5789) • G62(4868) • G63(26997) • G64(8735) • G65(5558) • G66(6360) • G67(6940) • G70(9541) • G72(6998) • G77(9926) • G81(14030)

The solution in the output files is represented as a string of size n, where n is the number of vertices. The ith element has value 1 if the ith vertex is placed to the first partition subset, otherwise its value is 2.