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

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

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

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