| 一种求解下模集函数最大值问题的近似算法 |
| |
| 引用本文： | 李小平,王利红,何尚录.一种求解下模集函数最大值问题的近似算法[J].黑龙江科技学院学报,2010,20(5):391-394. |
| |
| 作者姓名： | 李小平 王利红 何尚录 |
| |
| 作者单位： | 兰州交通大学数理与软件工程学院,兰州730070 |
| |
| 摘 要： | 下模集函数最大值问题属于NP-难问题，难以得到有效的求解方法。针对这一情况，运用概率分布方法，给出了求解该问题的一种近似算法，并证明算法的性能保证为1／3。组合优化问题实例证明了该算法的有效性。该研究可为求解下模集函数最大值问题提供新的思路。
|
| 关 键 词： | 下模集函数 最大值问题 近似算法 性能保证 组合优化问题 |
New approximation algorithm for maximizing submodular set function |
| |
| LI Xiaoping,WANG Lihong,HE Shanglu.New approximation algorithm for maximizing submodular set function[J].Journal of Heilongjiang Institute of Science and Technology,2010,20(5):391-394. |
| |
| Authors: | LI Xiaoping WANG Lihong HE Shanglu |
| |
| Institution: | (School of Mathematics, Physics ＆ Software Engineering, Lanzhou Jiaotong University, Lanzhou 730070, China) |
| |
| Abstract: | Targeted at difficulties due to an effective algorithm for the problem of maximizing a submodular set function classified as NP-hards, this paper gives a new approximation algorithm for maximizing submodular set functions by means of probability distribution. The paper proves that the performance guarantee of this algorithm is 1/3. The effect of this algorithm is illustrated by using a combinatorial optimization problem. This study provides a new idea for solving maximizing submodular set function. |
| |
| Keywords: | submodular set function maximum value problem approximation algorithm performance guarantee combinatorial optimization problem |
| 本文献已被 维普 万方数据 等数据库收录！ |
