局所点連結制約を持つ供給点配置問題に対する近似アルゴリズム
スポンサーリンク
概要
- 論文の詳細を見る
供給点配置問題とは,無向グラフにおいて供給点集合と各節点の間の連結度が節点の要求以上になるような最小コスト供給点集合を求める問題である.ただし本報告では,供給点集合Sと節点v間の連結度はv以外に節点を共有しないパスの最大本数と定義される.我々は供給点配置問題について,最大要求量がd^*の場合に対するO(d^* log d^*)近似アルゴリズムを提案する.また,供給点配置問題に関係する新たな問題を定義し,その問題に対する近似アルゴリズムを提案する.
- 2011-04-15
著者
関連論文
- 劣モジュラシステム分割問題に対するアルゴリズム
- Support Vector Machineにおけるルールの利用(線形計画)
- 無向グラフにおける集合連結問題
- 辺連結度制約と次数制約をもつネットワーク設計問題
- 全域木詰め込みに基づいたハイパーグラフ分割
- 組合せの効率的な生成法 (計算機科学とアルゴリズムの数理的基礎とその応用)
- 長さに上限をもつパスによる有向グラフの被覆に対するアルゴリズム
- 局所点連結制約を持つ供給点配置問題に対する近似アルゴリズム
- 局所辺連結度を保存するオイラーグラフ節点分離
- 重み付き次数制約を持つネットワーク設計問題
- 1-D-1 Algorithms for Covering Digraphs by Length-Bounded Walks