K-Median問題的近似計算復(fù)雜度與局部搜索近似算法分析.pdf

1、本文首先闡述k-median問題及其相關(guān)問題的研究背景,然后介紹兩個經(jīng)典的求解Metric k-median問題的近似算法,之后重點闡述本文所做的主要工作和創(chuàng)新點,討論一般距離空間下的k-median問題,其中的距離不一定滿足三角不等式,但保證距離是對稱的.設(shè)d<,max>/d<,min>表示k-median實例中與客戶點鄰接的最長邊長比最短邊長的最大者.首先證明d<,max>/d<,min>≤ω+ε的k-median問題不存在近似度小

2、于1+ω-1/e的多項式時間近似算法,除非NP(包含或等于)DTIME(n<'O(loglogn)>),由此可推出Metrick-median問題不可近似到1+2/e,除非NP(包含或等于)DTIME(n<'O(loglogn)>).然后給出一般距離空間下k-median問題的一個局部搜索算法,新的分析表明若有d<,max>/d<,min>≤ω,則局部搜索算法的近似度為1+ω-1/2.該結(jié)果亦適用于Metrick-median.ω≤5時

3、,局部搜索算法求解Metric k-median的近似度為3,好于現(xiàn)有結(jié)果3+2/p[10],多年以來研究者們一直在尋找Metrick-median近似度不超過3的多項式時間近似算法,而本文恰好找到一類Metric k-median問題子問題滿足上述條件.最后通過計算機實驗進一步研究了k-median局部搜索求解算法的實際計算效果和該算法的改進方法.實驗結(jié)果表明本文提出的針對一般距離空間下的k-median問題局部搜索算法在運行效率和求