k-median近似计算复杂度与局部搜索近似算法分析

k-median问题的近似算法研究一直是计算机科学工作者关注的焦点,现有研究结果大多是关于欧式空间和metric空间的,一般距离空间k-median的结果多年来一直未见.考虑一般距离空间k-median问题,设dmax/dmin表示k-median实例中与客户点邻接的最长边长比最短边长的最大者.首先证明dmax/dmin≤ω+ε的k-median问题不存在近似度小于1+ω-1/e的多项式时间近似算法,除非,由此推出metrick-median问题不可近似到1+2/e,除非np(∈)dtme(no(loglogn)).然后给出k-median问题的一个局部搜索算法,分析表明,若有dmax/dmin≤ω,则算法的近似度为1+ω-1/2.该结果亦适用于metrick-median,ω≤5时,局部搜索算法求解metrick-median的近似度为3,好于现有结果3+2/p.通过计算机实验,进一步研究了k-median局部搜索求解算法的实际计算效果和该算法的改进方法.