代表的施設配置近似アルゴリズムの実験的性能評価

• Item type: SIG Technical Reports(1)
• 公開日: 2003-01-20
• タイトル: 代表的施設配置近似アルゴリズムの実験的性能評価
• タイトル / 言語: en
• タイトル: Experimental Performance of Representative Approximation Algorithms for the Metric Facility Location Problem
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 中央大学大学院理工学研究科情報工学専攻
• 著者所属: 中央大学大学院理工学研究科情報工学専攻
• 著者所属(英): en
• 著者所属(英): Information and Systems Engineering Course, Graduate School of Science and Engineering, Chuo University
• 著者所属(英): en
• 著者所属(英): Information and Systems Engineering Course, Graduate School of Science and Engineering, Chuo University
• 著者名: 九里, 史郎; 浅野, 孝夫
• 著者名(英): Shiro, Kunori; Takao, Asano
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 施設は位置問題とは、人々が効率良く施設を利用するために開設する施設を決める問題である。この問題は現実的な環境において頻繁に発生する問題であり、ｋメディアン問題、ｋセンター問題など様々な関連問題が考えられている。本稿では、容量制限なしメトリック施設配置問題に対して、相対フィット法に基づく代表的な近似アルゴリズムの実験的性能評価を行う。そして、現在最も良い1.52近似アルゴリズムに対しても、局所改善を施して実験的性能評価を行い有効性を調べる。
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: The facility location problem is to decide which facilities are open to use them effectively. This problem appears frequently in real environments, and various related problems have been proposed such as k-median and k-center problems. In this paper, we evaluate experimental performance of representative algorithms for the metric uncapacitated facility location problem including algorithms that are analyzed by dual fitting method. We also propose some heuristics for the best known 1.52-approximation algorithm.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN1009593X
• 書誌情報: 情報処理学会研究報告アルゴリズム（AL）; 巻 2003, 号 3(2002-AL-088), p. 9-16, 発行日 2003-01-20
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会