| 求解非减上模集函数最小值问题的近似算法及其性能保证 |
| |
| 引用本文： | 郝自军,高岳林,何尚录.求解非减上模集函数最小值问题的近似算法及其性能保证[J].数学的实践与认识,2012,42(24). |
| |
| 作者姓名： | 郝自军 高岳林 何尚录 |
| |
| 作者单位： | 1. 北方民族大学信息与计算科学学院,宁夏银川,750021
2. 兰州交通大学数理与软件工程学院,甘肃兰州,730070 |
| |
| 基金项目： | 国家自然科学基金项目，北方民族大学基础研究计划项目 |
| |
| 摘 要： | 上模集函数的优化问题在组合优化问题中有广泛应用,许多组合优化问题,如设备选址问题、p-中心问题等都可化为上模集函数的优化问题.本文给出了求解非减上模集函数最小值问题的一种近似算法,并讨论了所给算法的性能保证.
|
| 关 键 词： | 组合优化问题 上模集函数 近似算法 性能保证 |
An Approximation Algorithm and Its Performance Guarantee for Minimizing Non-decreasing Supermodular Set Function |
| |
| HAO Zi-jun
,
GAO Yue-lin
,
HE Shang-lu.An Approximation Algorithm and Its Performance Guarantee for Minimizing Non-decreasing Supermodular Set Function[J].Mathematics in Practice and Theory,2012,42(24). |
| |
| Authors: | HAO Zi-jun GAO Yue-lin HE Shang-lu |
| |
| Abstract: | Maximizing or minimizing supermodular set function has a wide range of applications in combinatorial optimization problem.Many combinatorial optimization problems including equipment site selection or p-median problem can be translated into the supermodular set function's optimization problems.In this paper,an approximation algorithm for minimizing non-decreasing supermodular set function is presented,and its performance guarantee is discussed. |
| |
| Keywords: | combinatorial optimization problem supermodular set function approximation algorithm performance guarantee |
| 本文献已被 万方数据 等数据库收录！ |
