容量制限付きk-center問題の近似解法の実験的評価
スポンサーリンク
概要
- 論文の詳細を見る
k-center問題はNP最適化問題の中でも重要なものの一つである.容量制限付きk-center問題は, k-center問題のより現実的な設定である.容量制限付きk-center問題に対する, これまでに知られる最も良い近似アルゴリズムの近似率は6であるが, これは実用的でないと思われる.本稿では容量制限付きk-center問題に対する3つの発見的手法を示す.そのうちの2つを組み合わせることで, 従来手法よりも高速でかつ良い解が得られることを実験により示す.
- 一般社団法人情報処理学会の論文
- 2000-01-17
著者
関連論文
- 3次元グラフ構造の最大共通部分を求めるアルゴリズム
- 点パターンマッチングアルゴリズムの効率化
- 木の最大類似部分問題とそのアルゴリズム
- 二つの外平面描写の最大共通部分の抽出について
- 木の描写アルゴリズムの効率化
- 線図形の類似度とその計算法
- 根がなく巡回的順序がある木の間の距離とその計算法
- 大型データベースのための最長共通部分列の一高速抽出法
- 大型データペースのための最長共通部分列の一高速抽出法
- D-1-2 グラフ描画アルゴリズムに基づいたデフォルメ路線図作成法(D-1. コンピュテーション, 情報・システム1)