k-Median 问题的近似算法研究一直是计算机科学工作者关注的焦点,现有研究结果大多是关于欧式空间和 Metric 空间的,一般距离空间 k-Median 的结果多年来一直未见.考虑一般距离空间 k-Median 问题,设 dmax/dmin表示 k-Median 实例中与客户点邻接的最长边长比最短边长的最大者.首先证明 dmax/dmin≤ω+ε的 k-Median 问题不存在近似度小于1+ ω ?1 (loglog n) e 的多项式时间近似算法...
科研之友
微信
新浪微博
Facebook
分享链接
