图的最大二等分问题的秩二松弛算法的改进  

Improvement on the Rank-two Relaxation Algorithm for the Graph Max-bisection Problem

作　　者：张芳[1] 徐成贤[1] 

机构地区：[1]西安交通大学理学院,西安710049

出　　处：《工程数学学报》2010年第4期621-626,共6页Chinese Journal of Engineering Mathematics

摘　　要：本文在吸取半定规划松弛和秩二松弛方法的优点,克服其缺点的基础上,针对模型目标函数非凸的特点,提出了图的最大二等分问题的秩二松弛模型。由于该模型变量的数目没有增加,因此该方法对求解大规模问题很有优势。数值实验表明,这种算法无论是与半定规划松弛还是原秩二松弛算法相比,在获得目标函数值相当的情况下,运行时间较短。A rank-two relaxation model is proposed for the graph max-bisection problem. The ap- proach is based on theories of SDP and rank-two relaxation approaches, and the approach utilizes the character that the objective function is non-convex in the model. Since the number of variables does not increase, this approach is suitable for large-scale problems. Extensive numerical experiments show that, compared with the SDP and the original rank-two relaxation approaches, our algorithm need less time to approach the similar value of objective function.

关 键 词：图的最大二等分问题 秩二松弛 拟NEWTON法 

分 类 号：O221.2[理学—运筹学与控制论]