最小マンハッタンネットワーク問題に対する近似アルゴリズム
スポンサーリンク
概要
- 論文の詳細を見る
平面上に与えられたn個の点集合Sに対して, どの2点間にも2点間のL_1-距離に等しい長さのパスが存在するネットワークをSのマンハッタンネットワークという.最小マンハッタンネットワーク問題は, このようなネットワークのうちで, 辺の長さの総和(辺長和)が最小となるものを求める問題である.現在, この問題に対して最適解を求める多項式時間のアルゴリズムは知られておらず, 既知の(多項式時間)近似アルゴリズムの最良の近似精度は4である.本論文では, この問題に対する2近似アルゴリズムを提案する.
- 一般社団法人情報処理学会の論文
- 2002-01-24
著者
-
今井 桂子
中央大学理工学部
-
浅野 孝夫
中央大学理工学部情報工学科
-
Ono T
Graduate School Of Information Science Nagoya University
-
加藤 亮
中央大学大学院理工学研究科情報工学専攻
関連論文
- 安全性を考慮した集団下校経路の作成 : 階層型施設配置モデルの適用(子どもを守る・育む)
- NP-completeness of generalized Kaboozle (コンピュテーション)
- 単純多角形の生成に関する発見的手法(セッション2)
- 日本応用数理学会創立10周年記念講演会 : パネル討論会「応用数理の未来」(10周年記念)
- 入力された形状を考慮したスケッチによるメッシュの表面特徴の変形(セッション2:モデリング・認識)
- 眼底断層画像の領域抽出・解析手法に関する研究 : 緑内障診断に用いられる視神経構造特徴の自動測定(一般,First Person Visionのための認識・理解)
- 衝突確率を考慮したバッファ配置問題に対する計算機シミュレーションを利用した手法
- 2-C-9 地図の拡大・縮小表示を念頭に置いたNLP問題に対するラベルサイズ最大化(公共関連(2))
- 搬送計画問題に対するネットワーク理論を利用したアプローチ
- 組合せ最適化問題に対する効率的手法