最小マンハッタンネットワーク問題に対する近似アルゴリズム

• Item type: SIG Technical Reports(1)
• 公開日: 2002-01-24
• タイトル: 最小マンハッタンネットワーク問題に対する近似アルゴリズム
• タイトル / 言語: en
• タイトル: An Approximation Algorithm for the Minimum Manhattan Network Problem
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 中央大学大学院理工学研究科情報工学専攻
• 著者所属: 中央大学理工学部情報工学科
• 著者所属: 中央大学理工学部情報工学科
• 著者所属(英): en
• 著者所属(英): Information and System Engineering Course Graduate School of Science and Engineering, Chuo University
• 著者所属(英): en
• 著者所属(英): Department of Information and System Engineering, Chuo University
• 著者所属(英): en
• 著者所属(英): Department of Information and System Engineering, Chuo University
• 著者名: 加藤亮; 今井, 桂子; 浅野, 孝夫
• 著者名(英): Ryo, Kato; Keiko, Imai; Takao, Asano
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 平面上に与えられたn個の点集合Sに対して、どの２点間にも２点間のL1-距離に等しい長さのパスが存在するネットワークをSのマンハッタンネットワークという．最小マンハッタンネットワーク問題は、このようなネットワークのうちで、辺の長さの総和（辺長和）が最小となるものを求める問題である．現在、この問題に対して最適解を求める多項式時間のアルゴリズムは知れておらず、既知の(多項式時間）近似アルゴリズムの最良の近似精度は4である．本論文では、この問題に対する２近似アルゴリズムを提案する。
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: For a given set S of n points in the plane, a manhattan network for S is a network in which,for each pair of points in S, there is a path between them of length equal to their L1-distance. The minimum manhattan network problem is a problem of finding a manhattan network of minimum length. For this problem, no polynomial time exact algorithm has been known and a 4 approximation algorithm has been proposed. In this paper, we improve this bound and present a 2 approximation algorithm.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN1009593X
• 書誌情報: 情報処理学会研究報告アルゴリズム（AL）; 巻 2002, 号 7(2001-AL-082), p. 1-8, 発行日 2002-01-24
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会