%0 Journal Article
%T Randomized Reverse Greedy Algorithm for k-median Problem<br>k-median问题反向贪心随机算法
%A WANG Shou-qiang
%A <br>王守强
%J 计算机科学
%D 2012
%I 
%X k-median问题的近似算法研究一直是计算机科学工作者关注的焦点。基于均衡限制条件,利用反向贪心策略,给出求解该问题的随机近似算法。证明该算法以较大的概率满足其近似性能比的期望值为(3+O(ln(ln(k)/α))。该算法的时间复杂度为O(kαln(k)]2(n+m)),其中n和m分别代表设施集合以及客户点集的大小。最后,通过计算机实验验证了k-median问题的反向贪心算法的实际计算效果。
%K k- median
%K Randomized algorithm
%K Reverse greedy
%K Aapproximation ratio<br>k-median
%K 随机算法
%K 反向贪心
%K 近似性能比
%U http://www.alljournals.cn/get_abstract_url.aspx?pcid=5B3AB970F71A803DEACDC0559115BFCF0A068CD97DD29835&cid=8240383F08CE46C8B05036380D75B607&jid=64A12D73428C8B8DBFB978D04DFEB3C1&aid=F0F98CE13E99B5070535920E3CBCBC1F&yid=99E9153A83D4CB11&vid=7C3A4C1EE6A45749&iid=DF92D298D3FF1E6E&sid=E1D946F217E3B046&eid=FBCA02DBD05BD4EA&journal_id=1002-137X&journal_name=计算机科学&referenced_num=0&reference_num=0