Abstract
為各種設施找出最佳的放置地點是一個日常生活中實際而且有著廣泛應用的問題，從交通運輸到網路通訊方面的設施設置問題都屬於這個領域，因此長久以來一直廣泛受到學者們的討論與研究。在Location theory 上最具有代表性也最重要的兩個問題，是 p 中心 (p-center) 問題以及 p 重心 (p-median) 問題。p-center 問題的定義是要放置 p 個伺服器，希望在服務所有使用者的花費中最貴的那一個能夠越便宜越好，而 p-median 問題則是要求服務所有使用者之花費的總和必須越小越好。 傳統上都將服務某一個使用者的花費定義為使用者到其最近伺服器的加權 (weighted) 距離，但某些設施的服務方式並不只是單純將服務送到使用者端而已，有時候還會需要在某些轉運站 (depot) 拿取物品或卸下貨物。Drezner 跟 Wesolowsky 於是提出了環形路徑 (round-trip) 模型。在這模型中，有一個轉運站集合稱為 X ，使用者可以使用任何一個 X 中的轉運站。他們將某一個使用者的服務距離定義為從伺服器到轉運站到使用者再回到伺服器的路徑長(注意他們會選擇使用能讓服務距離最短的伺服器以及轉運站)。而服務某一個使用者的花費就是加權的服務距離。之後，Tamir 跟 Halman 對這個問題提出一個延伸的版本。他們限制服務使用者 ci 時只能使用某些轉運站(這些轉運站的集合稱為 Xi )。他們將這個版本稱為限制版本 (restricted version)，並將原問題稱為無限制版本 (unrestricted version)。另外他們還提出了兩個延伸的服務模型，稱為使用者單向路徑 (customer one-way) 模型以及轉運站單向路徑 (depot one-way) 模型，其中使用者單向路徑模型不計算使用者到伺服器之間的距離，而轉運站單向路徑模型不計算轉運站到伺服器之間的距離。 本篇論文所探討的就是在一個廣義圖 (general graph) G = (V, E) 中尋找環形路徑模型以及使用者單向路徑模型下的最佳服務設施設置地點。本論文改進了在環形路徑以及使用者單向路徑模型下尋找一個中心 (center) 的演算法，將原本 O(mnlog n + m□i|Xi|) 時間的演算法加速到 O(mnlog n) 的時間，其中 m = |E| 而 n = |V|。若考慮不加權 (unweighted) 的情況並限制轉運站都在節點上，這個演算法可以再加速到 O(mnloglog n + n2 log n) 的時間。上述演算法所使用的技巧同樣可以套用在環形路徑以及使用者單向路徑模型下尋找一個重心 (median) 的問題，並且改進之前演算法的時間。