软件学报
軟件學報
연건학보
JOURNAL OF SOFTWARE
2005年
3期
392-399
,共8页
潘锐%朱大铭%马绍汉%肖进杰
潘銳%硃大銘%馬紹漢%肖進傑
반예%주대명%마소한%초진걸
k中间点%算法%局部搜索%近似度%设备%客户
k中間點%算法%跼部搜索%近似度%設備%客戶
k중간점%산법%국부수색%근사도%설비%객호
k-Median问题的近似算法研究一直是计算机科学工作者关注的焦点,现有研究结果大多是关于欧式空间和Metric空间的,一般距离空间k-Median的结果多年来一直未见.考虑一般距离空间k-Median问题,设dmax/dmin表示k-Median实例中与客户点邻接的最长边长比最短边长的最大者.首先证明dmax/dmin≤ω+ε+(的k-Median问题不存在近似度小于1+ω-1/e的多项式时间近似算法,除非,由此推出Metric k-Median问题不可近似到1+2/e,除非NP(∈)DTME(NOlog logn)).然后给出k-Median问题的一个局部搜索算法,分析表明,若有dmax/dmin≤ω,则算法的近似度为1+ω-1/2.该结果亦适用于Metric k-Median,ω≤5时,局部搜索算法求解Metric k-Median的近似度为3,好于现有结果3+2/P.通过计算机实验,进一步研究了k-Median局部搜索求解算法的实际计算效果和该算法的改进方法.
k-Median問題的近似算法研究一直是計算機科學工作者關註的焦點,現有研究結果大多是關于歐式空間和Metric空間的,一般距離空間k-Median的結果多年來一直未見.攷慮一般距離空間k-Median問題,設dmax/dmin錶示k-Median實例中與客戶點鄰接的最長邊長比最短邊長的最大者.首先證明dmax/dmin≤ω+ε+(的k-Median問題不存在近似度小于1+ω-1/e的多項式時間近似算法,除非,由此推齣Metric k-Median問題不可近似到1+2/e,除非NP(∈)DTME(NOlog logn)).然後給齣k-Median問題的一箇跼部搜索算法,分析錶明,若有dmax/dmin≤ω,則算法的近似度為1+ω-1/2.該結果亦適用于Metric k-Median,ω≤5時,跼部搜索算法求解Metric k-Median的近似度為3,好于現有結果3+2/P.通過計算機實驗,進一步研究瞭k-Median跼部搜索求解算法的實際計算效果和該算法的改進方法.
k-Median문제적근사산법연구일직시계산궤과학공작자관주적초점,현유연구결과대다시관우구식공간화Metric공간적,일반거리공간k-Median적결과다년래일직미견.고필일반거리공간k-Median문제,설dmax/dmin표시k-Median실례중여객호점린접적최장변장비최단변장적최대자.수선증명dmax/dmin≤ω+ε+(적k-Median문제불존재근사도소우1+ω-1/e적다항식시간근사산법,제비,유차추출Metric k-Median문제불가근사도1+2/e,제비NP(∈)DTME(NOlog logn)).연후급출k-Median문제적일개국부수색산법,분석표명,약유dmax/dmin≤ω,칙산법적근사도위1+ω-1/2.해결과역괄용우Metric k-Median,ω≤5시,국부수색산법구해Metric k-Median적근사도위3,호우현유결과3+2/P.통과계산궤실험,진일보연구료k-Median국부수색구해산법적실제계산효과화해산법적개진방법.
