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

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

给出求解一般最大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.