图的最大二等分问题的低秩可行方向算法

穆学文;刘红卫;刘三阳

系统科学与数学 ›› 2007, Vol. 27 ›› Issue (5) : 780-790.

PDF(397 KB)
中国科学院数学与系统科学研究院期刊网
PDF(397 KB)
系统科学与数学 ›› 2007, Vol. 27 ›› Issue (5) : 780-790. DOI: 10.12341/jssms10019
论文

图的最大二等分问题的低秩可行方向算法

    穆学文, 刘红卫, 刘三阳
作者信息 +

A Feasible Direction Algorithm for Max Bisection via Low-RankFactorization

    Mu Xuewen, Liu Hongwei, Liu Sanyang
Author information +
文章历史 +

摘要

基于图的最大二等分问题的半定规划松弛模型,利用矩阵的低秩分解技巧,给出了该问题的半定规划松弛的一种低秩可行方向算法.在一定的条件下，证明了算法的收敛性.结合0.699随机扰动方法得到原问题的近似最优解.数值实验表明该方法能有效地求解图的最大二等分问题.

Abstract

Based on the semidefinite programming relaxation of {\rm max} Bisection, a feasible direction algorithm is given to solve the relaxation. Coupled with the 0.699 randomized method, the approximate solution of {\rm max} Bisection is obtained. Furthermore, its convergent result is given. The numerical experiment shows that the algorithm can solve the {\rm max} Bisection efficiently.

关键词

图的最大二等分问题 / 半定规划松弛 / 可行方向算法 / 随机扰动.

Key words

Max bisection problem / semidefinite programming relaxation / feasible direction / randomized method.

引用本文

EndNote

Ris (Procite)

Bibtex

导出引用
穆学文 , 刘红卫 , 刘三阳. 图的最大二等分问题的低秩可行方向算法. 系统科学与数学, 2007, 27(5): 780-790. https://doi.org/10.12341/jssms10019
Mu Xuewen , Liu Hongwei , Liu Sanyang. A Feasible Direction Algorithm for Max Bisection via Low-RankFactorization. Journal of Systems Science and Mathematical Sciences, 2007, 27(5): 780-790 https://doi.org/10.12341/jssms10019
中图分类号： 93C35   
PDF(397 KB)

169

Accesses

0

Citation

Detail
段落导航
相关文章

/

〈 〉