求解一般最大p-设施定位问题的贪婪算法及其性能保证  

The Greedy Algorithm for a Generalization of the Maximum p-Facility Locationproblem and its Performance Guarantee

作　　者：王武民[1] 张防防[1] 柘晓莉[1] 何尚录[1] 

机构地区：[1]兰州交通大学数理与软件工程学院,甘肃兰州730070

出　　处：《咸阳师范学院学报》2008年第2期17-18,共2页Journal of Xianyang Normal University

摘　　要：给出求解一般最大P-设施定位问题的贪婪算法并证明了该算法的性能保证为(1-e-(k+1))/(k+1)。其思想是从某一个初始解出发,通过一系列的贪婪选择当前状态下的最优解,逐步逼近给定的目标,当达到算法中的某一步不能再继续前进时,算法停止。This paper consider a Generalization of Maximum the facility location,We prove that the simple greedy algorithm has performance guarantee, its idea is from one of the initial solutions, through a series of greedy choice under the current state of the optimal choice, and gradually approaching to the target set,when the algorithm to achieve a step can not continue to move forward, the algorithm to stop.

关 键 词：组合优化问题 贪婪算法 性能保证 

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