论文部分内容阅读
κ-Median问题的近似算法研究一直是计算机科学工作者关注的焦点，现有研究结果大多是关于欧式空间和Metric空间的，一般距离空间κ-Median的结果多年来一直未见．考虑一般距离空间κ-Median问题，设dmax／dmin表示k-Median实例中与客户点邻接的最长边长比最短边长的最大者，首先证明dmax/dmin≤ω+ε的κ-Median问题不存在近似度小于1+ω-1/e的多项式时间近似算法，除非NP包含于DTIME（n^O(log longn),由此推出Metric κ-Median问题不可近似