| 给定部分大小的最大有向割问题的一种近似方法 |
| |
| 引用本文： | 王莲花,郝自军,张玉栋,何尚录. 给定部分大小的最大有向割问题的一种近似方法[J]. 兰州交通大学学报, 2006, 25(1): 148-150 |
| |
| 作者姓名： | 王莲花 郝自军 张玉栋 何尚录 |
| |
| 作者单位： | 兰州交通大学,数理与软件工程学院,甘肃,兰州,730070;兰州交通大学,数理与软件工程学院,甘肃,兰州,730070;兰州交通大学,数理与软件工程学院,甘肃,兰州,730070;兰州交通大学,数理与软件工程学院,甘肃,兰州,730070 |
| |
| 摘 要： | 给出了求解给定部分大小的最大有向割问题的一种新的近似方法,并讨论了它的性能保证.该方法的核心是利用Pipage技术,并结合线性松驰的基本解的特性,为给定部分大小的最大有向割问题设计出了0.5-近似算法.
|
| 关 键 词： | 最大有向割问题 近似方法 性能保证 ε-凸性 |
| 文章编号： | 1001-4373(2006)01-0148-03 |
| 收稿时间： | 2005-06-15 |
| 修稿时间： | 2005-06-15 |
An Approximate Method for Max Dicut with Given Size of Parts |
| |
| Wang Lianhua,Hao Zijun,Zhang Yudong,He Shanglu. An Approximate Method for Max Dicut with Given Size of Parts[J]. Journal of Lanzhou Jiaotong University, 2006, 25(1): 148-150 |
| |
| Authors: | Wang Lianhua Hao Zijun Zhang Yudong He Shanglu |
| |
| Abstract: | A new approximate method is presented for max dicut problem with given size of the parts,and its performance guarantee is analysed.The core of the method is the technique based on exploiting structure properties of basic solutions to a linear relaxation.By using the method,a approximate algorithm is presented. |
| |
| Keywords: | max dicut problem approximate method performance guarantee convexity |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
|
