【摘要】 上模集函数的优化问题在组合优化问题中有广泛应用,许多组合优化问题,如设备选址问题、p-中心问题等都可化为上模集函数的优化问题.本文给出了求解非减上模集函数最小值问题的一种近似算法,并讨论了所给算法的性能保证.更多还原

【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.更多还原