The　max-cut　problem　is　a　classical　NP-hard　problem　in　graph　theory.　In　this　paper,　we　adopt　a　local　search　method,　called　MCFM,　which　is　a　simple　modification　of　the　Fiduccia-Mattheyses　heuristic　method　in　Fiduccia　and　Mattheyses　(Proc.　ACM/IEEE　DAC,　pp.　175-181,　1982)　for　the　circuit　partitioning　problem　in　very　large　scale　integration　of　circuits　and　systems.　The　method　uses　much　less　computational　cost　than　general　local　search　methods.　Then,　an　auxiliary　function　is　presented　which　has　the　same　global　maximizers　as　the　max-cut　problem.　We　show　that　maximization　of　the　function　using　MCFM　can　escape　successfully　from　previously　converged　discrete　local　maximizers　by　taking　increasing　values　of　a　parameter.　An　algorithm　is　proposed　for　the　max-cut　problem,　by　maximizing　the　auxiliary　function　using　MCFM　from　random　initial　solutions.　Computational　experiments　were　conducted　on　three　sets　of　standard　test　instances　from　the　literature.　Experimental　results　show　that　the　proposed　algorithm　is　effective　for　the　three　sets　of　standard　test　instances.　©　2012　Springer　Science+Business　Media,　LLC.