求解非减上模集函数最小值问题的近似算法及其性能保证  

An Approximation Algorithm and Its Performance Guarantee for Minimizing Non-decreasing Supermodular Set Function

作　　者：郝自军[1] 高岳林[1] 何尚录[2] 

机构地区：[1]北方民族大学信息与计算科学学院,宁夏银川750021 [2]兰州交通大学数理与软件工程学院,甘肃兰州730070

出　　处：《数学的实践与认识》2012年第24期142-148,共7页Mathematics in Practice and Theory

基　　金：国家自然科学基金项目(10901004);北方民族大学基础研究计划项目

摘　　要：上模集函数的优化问题在组合优化问题中有广泛应用,许多组合优化问题,如设备选址问题、p-中心问题等都可化为上模集函数的优化问题.本文给出了求解非减上模集函数最小值问题的一种近似算法,并讨论了所给算法的性能保证.Maximizing or minimizing supermodular set function has a wide range of appli- cations in combinatorial optimization problem. Many combinatorial optimization problems including equipment site selection or p-median problem can be translated into the super- modular 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.

关 键 词：组合优化问题 上模集函数 近似算法 性能保证 

分 类 号：O224[理学—运筹学与控制论]