Abstract
在平面上給n 個帶有權重的需求點，其直角距離之m 中心問題為：求m 個服務點，使需求點與其最近的服務點的加權直角距離中最大的最小。如需求點的權重皆相同，稱之為無加權m 中心問題；否則，稱之為加權m 中心問題。直角距離之m 中心問題為最重要的服務設施設置地點問題之一，適合於模擬城市地區緊急服務設施之設置。當m 視為輸入參數時，直角距離之m 中心問題已被證明為NP- 完備。在此論文，更進一步被證明其任何多項式時間的近似演算法的最壞狀況誤差比例大於或等於２，除非NP＝P 。且我們也提出一多項式時間，最壞狀況誤差比例恰為２的近似演算法。當m 視為常數時，對於無加權直角距離之m 中心問題，m 大於或等於４，我們提出O（n^(m-2) ㏒ n）時間的演算法，改進前人O （n^(2m-5) ㏒ n） 時間的演算法。對於加權直角距離之雙中心問題和三中心問題，我們各提出近乎最佳時間複雜度的O （n ㏒ n）時間的演算法。概念上，這些演算法都利用需求點集合的上、下、左、右四種極點來限制服務點的選取範圍以得到相當少數的候選解，而最佳解就在候選解之中。