Given　an　undirected　graph　with　edge　weights,　the　max-cut　problem　is　to　find　a　partition　of　the　vertices　into　two　subsets,　such　that　the　sum　of　the　weights　of　the　edges　crossing　different　subsets　is　maximized.　Heuristics　based　on　auxiliary　function　can　obtain　high-quality　solutions　of　the　max-cut　problem,　but　suffer　high　solution　cost　when　instances　grow　large.　In　this　paper,　we　combine　clustered　adaptive　multistart　and　discrete　dynamic　convexized　method　to　obtain　high-quality　solutions　in　a　reasonable　time.　Computational　experiments　on　two　sets　of　benchmark　instances　from　the　literature　were　performed.　Numerical　results　and　comparisons　with　some　heuristics　based　on　auxiliary　function　show　that　the　proposed　algorithm　is　much　faster　and　can　obtain　better　solutions.　Comparisons　with　several　state-of-the-science　heuristics　demonstrate　that　the　proposed　algorithm　is　competitive.　©　2014　Operations　Research　Society　of　China,　Periodicals　Agency　of　Shanghai　University,　and　Springer-Verlag　Berlin　Heidelberg.