图的最大二等分问题的投影梯度算法

摘要：

本文基于图的最大二等分问题已有的半定规划松弛模型,给出了原问题的等价模型及其新的半定规划松弛模型,利用投影梯度算法求解该半定规划松弛模型,最后使用随机扰动算法求得原问题的近似最优解.理论和数值试验表明该方法不仅可以在较高的精度下求解中小规模的图的最大二等分问题,而且特别适合求解大规模的图的最大二等分问题.

关键词：图的最大二等分、半定规划、投影梯度算法、随机扰动

所属期刊栏目：22

分类号：O221.7(运筹学)

资助基金：国家自然科学基金69972036;陕西省自然科学基金2001SL05

在线出版日期：2005-03-24（万方平台首次上网日期，不代表论文的发表时间）

页数：共4页

页码：171-174