|
|||||
|
|
| 关于图划分问题的改进的近似算法 | |
| 引用本文： | 徐大川,韩继业,杜东雷. 关于图划分问题的改进的近似算法[J]. 应用数学学报, 2005, 28(4): 587-597 |
| 作者姓名： | 徐大川 韩继业 杜东雷 |
| 作者单位： | 1. 北京工业大学数理学院,北京,100022 2. 中国科学院数学与系统科学研究院应用数学研究所,北京,100080 3. 新布伦兹维克大学管理系,加拿大 |
| 基金项目： | 北京工业大学数理基金、博士科研启动基金,国家自然科学基金（10401038,10171108,10271002）,NSERC基金（10004901）资助项目. |
| 摘 要： | 本文考虑NP-难的极大图划分(MAX-GP)问题.我们给出应用半定规划(SDP) 松弛的一个一般方法,并且给出包括极大方向割,稠密子图,极大顶点覆盖,极大割,和极大反割在内的图划分问题的改进的近似比. |
| 关 键 词： | 图划分问题 近似算法 半定规划 |
| 收稿时间： | 2003-11-24 |
| 修稿时间： | 2003-11-24 |
IMPROVED APPROXIMATION ALGORITHM FOR GRAPH PARTITION PROBLEM |
|
| XU DACHUAN,HAN JIYE,DU DONGLEI. IMPROVED APPROXIMATION ALGORITHM FOR GRAPH PARTITION PROBLEM[J]. Acta Mathematicae Applicatae Sinica, 2005, 28(4): 587-597 | |
| Authors: | XU DACHUAN HAN JIYE DU DONGLEI |
| Affiliation: | College of Applied Sciences, Beijing University of Technology, Beijing 100022;Institute of Applied Mathematics, Academy of Mathematics and Systems Sciences, CAS, Beijing 100080;Faculty of Administration, University of New Brunswick, Canada |
| Abstract: | In this paper,we consider maximum graph partition problem which is NP-hard. We propose a general method to design the approximation algorithm using semidefinite programming(SDP).Improved approximation ratios for max dicut,dense-subgraph,max vertex-cover,max cut,max uncut are listed at several tables. |
| Keywords: | Graph partition problem approximation algorithm semidefinite programming |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ | |