In this paper,we consider a class of quadratic maximization problems.For a subclass of the problems,we show that the SDP relaxation approach yields an approximation solution with the worst-case performance ratio at le...In this paper,we consider a class of quadratic maximization problems.For a subclass of the problems,we show that the SDP relaxation approach yields an approximation solution with the worst-case performance ratio at leastα=0.87856….In fact,the estimated worst-case performance ratio is dependent on the data of the problem withαbeing a uniform lower bound.In light of this new bound,we show that the actual worst-case performance ratio of the SDP relaxation approach (with the triangle inequalities added) is at leastα+δ_d if every weight is strictly positive,whereδ_d>0 is a constant depending on the problem dimension and data.展开更多
An effective continuous algorithm is proposed to find approximate solutions of NP-hard max-cut problems. The algorithm relaxes the max-cut problem into a continuous nonlinear programming problem by replacing n discret...An effective continuous algorithm is proposed to find approximate solutions of NP-hard max-cut problems. The algorithm relaxes the max-cut problem into a continuous nonlinear programming problem by replacing n discrete constraints in the original problem with one single continuous constraint. A feasible direction method is designed to solve the resulting nonlinear programming problem. The method employs only the gradient evaluations of the objective function, and no any matrix calculations and no line searches are required. This greatly reduces the calculation cost of the method, and is suitable for the solution of large size max-cut problems. The convergence properties of the proposed method to KKT points of the nonlinear programming are analyzed. If the solution obtained by the proposed method is a global solution of the nonlinear programming problem, the solution will provide an upper bound on the max-cut value. Then an approximate solution to the max-cut problem is generated from the solution of the nonlinear programming and provides a lower bound on the max-cut value. Numerical experiments and comparisons on some max-cut test problems （small and large size） show that the proposed algorithm is efficient to get the exact solutions for all small test problems andwell satisfied solutions for most of the large size test problems with less calculation costs.展开更多
A continuation algorithm for the solution of max-cut problems is proposed in this paper. Unlike the available semi-definite relaxation, a max-cut problem is converted into a continuous nonlinear programming by employi...A continuation algorithm for the solution of max-cut problems is proposed in this paper. Unlike the available semi-definite relaxation, a max-cut problem is converted into a continuous nonlinear programming by employing NCP functions, and the resulting nonlinear programming problem is then solved by using the augmented Lagrange penalty function method. The convergence property of the proposed algorithm is studied. Numerical experiments and comparisons with the Geomeans and Williamson randomized algorithm made on some max-cut test problems show that the algorithm generates satisfactory solutions for all the test problems with much less computation costs.展开更多
Given an undirected graph with edge weights,the max-cut problem is to find a partition of the vertices into twosubsets,such that the sumof theweights of the edges crossing different subsets ismaximized.Heuristics base...Given an undirected graph with edge weights,the max-cut problem is to find a partition of the vertices into twosubsets,such that the sumof theweights of the edges crossing different subsets ismaximized.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-ofthe-science heuristics demonstrate that the proposed algorithm is competitive.展开更多
基金This work was supported by the National Natural Science Foundation of China (Grant No.10401038)Startup Grant for Doctoral Research of Beijing University of Technology and Hong Kong RGC Earmarked Grant CUHK4242/04E
文摘In this paper,we consider a class of quadratic maximization problems.For a subclass of the problems,we show that the SDP relaxation approach yields an approximation solution with the worst-case performance ratio at leastα=0.87856….In fact,the estimated worst-case performance ratio is dependent on the data of the problem withαbeing a uniform lower bound.In light of this new bound,we show that the actual worst-case performance ratio of the SDP relaxation approach (with the triangle inequalities added) is at leastα+δ_d if every weight is strictly positive,whereδ_d>0 is a constant depending on the problem dimension and data.
基金This work is supported by National Natural Science Foundation of China at 10231060.
文摘An effective continuous algorithm is proposed to find approximate solutions of NP-hard max-cut problems. The algorithm relaxes the max-cut problem into a continuous nonlinear programming problem by replacing n discrete constraints in the original problem with one single continuous constraint. A feasible direction method is designed to solve the resulting nonlinear programming problem. The method employs only the gradient evaluations of the objective function, and no any matrix calculations and no line searches are required. This greatly reduces the calculation cost of the method, and is suitable for the solution of large size max-cut problems. The convergence properties of the proposed method to KKT points of the nonlinear programming are analyzed. If the solution obtained by the proposed method is a global solution of the nonlinear programming problem, the solution will provide an upper bound on the max-cut value. Then an approximate solution to the max-cut problem is generated from the solution of the nonlinear programming and provides a lower bound on the max-cut value. Numerical experiments and comparisons on some max-cut test problems （small and large size） show that the proposed algorithm is efficient to get the exact solutions for all small test problems andwell satisfied solutions for most of the large size test problems with less calculation costs.
基金Key Project supported by National Natural Science Foundation of China,10231060
文摘A continuation algorithm for the solution of max-cut problems is proposed in this paper. Unlike the available semi-definite relaxation, a max-cut problem is converted into a continuous nonlinear programming by employing NCP functions, and the resulting nonlinear programming problem is then solved by using the augmented Lagrange penalty function method. The convergence property of the proposed algorithm is studied. Numerical experiments and comparisons with the Geomeans and Williamson randomized algorithm made on some max-cut test problems show that the algorithm generates satisfactory solutions for all the test problems with much less computation costs.
基金supported partially by the National Natural Science Foundation of China(Nos.11226236 and 11301255)the Natural Science Foundation of Fujian Province of China(No.2012J05007)the Science and Technology Project of the Education Bureau of Fujian,China(Nos.JA13246 and JK2012037).
文摘Given an undirected graph with edge weights,the max-cut problem is to find a partition of the vertices into twosubsets,such that the sumof theweights of the edges crossing different subsets ismaximized.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-ofthe-science heuristics demonstrate that the proposed algorithm is competitive.
