  By introducing a quadratic perturbation to the canonical dual of the maxcut
problem, we transform the integer programming problem into a concave
maximization problem over a convex positive domain under some circumstances,
which can be solved easily by the well-developed optimization methods.
Considering that there may exist no critical points in the dual feasible
domain, a reduction technique is used gradually to guarantee the feasibility of
the reduced solution, and a compensation technique is utilized to strengthen
the robustness of the solution. The similar strategy is also applied to the
maxcut problem with linear perturbation and its hybrid with quadratic
perturbation. Experimental results demonstrate the effectiveness of the
proposed algorithms when compared with other approaches.
