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

摘要

给出求解一般最大P-设施定位问题的贪婪算法并证明了该算法的性能保证为(1-e-(k+1))/(k+1).其思想是从某一个初始解出发,通过一系列的贪婪选择当前状态下的最优解,逐步逼近给定的目标,当达到算法中的某一步不能再继续前进时,算法停止.