系统工程
繫統工程
계통공정
SYSTEMS ENGINEERING
2008年
10期
112-115
,共4页
运筹学%选址问题%占线中心%竞争比%一般网络
運籌學%選阯問題%佔線中心%競爭比%一般網絡
운주학%선지문제%점선중심%경쟁비%일반망락
对一般网络上的占线中心选址问题及其竞争算法进行了研究.文献[6]证明了该问题的竞争比下界是(n-2△e+√(n-22△e2+4(n-1)/2(n-1)) ,其中△e是所给空间最大的相对距离,并证明了该问题不存在常数竞争比的竞争算法.本文给出了一个多项式时间的竞争算法,并证明该算法的竞争比为△e△w,其中△w是所给空间点间的最大相对权重.所得结论不仅对于理论上占线中心选址问题的竞争算法的设计与分析,还是对于实际中的选址决策,都具有一定的指导意义.
對一般網絡上的佔線中心選阯問題及其競爭算法進行瞭研究.文獻[6]證明瞭該問題的競爭比下界是(n-2△e+√(n-22△e2+4(n-1)/2(n-1)) ,其中△e是所給空間最大的相對距離,併證明瞭該問題不存在常數競爭比的競爭算法.本文給齣瞭一箇多項式時間的競爭算法,併證明該算法的競爭比為△e△w,其中△w是所給空間點間的最大相對權重.所得結論不僅對于理論上佔線中心選阯問題的競爭算法的設計與分析,還是對于實際中的選阯決策,都具有一定的指導意義.
대일반망락상적점선중심선지문제급기경쟁산법진행료연구.문헌[6]증명료해문제적경쟁비하계시(n-2△e+√(n-22△e2+4(n-1)/2(n-1)) ,기중△e시소급공간최대적상대거리,병증명료해문제불존재상수경쟁비적경쟁산법.본문급출료일개다항식시간적경쟁산법,병증명해산법적경쟁비위△e△w,기중△w시소급공간점간적최대상대권중.소득결론불부대우이론상점선중심선지문제적경쟁산법적설계여분석,환시대우실제중적선지결책,도구유일정적지도의의.
