グラフの点集合間連結性に関するアルゴリズムの研究

点击翻译按钮获取中文摘要

節点の重み付き次数について上限制約をもつネットワーク設計問題に対し,近似アルゴリズムの開発を行った.ここで重み付き次数とは,節点に接続する辺に与えられている重みの和のことであり,例えばグラフがある通信ネットワークを表している場合は,そのネットワーク上の各ノードに集中する負荷の大きさを表現するものである.問題はそれぞれの節点に対して重み付き次数の上限を与えたうえで,さらに必要な連結度の要求を満たすグラフの中でコスト最小のものを求める.連結度の要求が全域木であることを求めるものであるとき,我々の提案アルゴリズムは,重み付き次数上限制約を4倍違反することを許した上で,最適コストの解を計算する.また連結度要求が弱優モジュラカット関数によって与えられている場合,重み付き次数上限制約を7倍違反することを許した上で,最適コストに対して2倍の近似精度を達成する.また,これらのアルゴリズムは,コストではなく最大重み付き次数を最小化する問題や,各辺に定義された重みを両端点に分配することを許すなどのより一般的な設定を持つ問題にも適用可能である.設計手法としては,近年(重みなし)次数上限付きネットワーク設計問題への適用に関する研究が盛んなIterative Rounding法(線形計画緩和解を繰り返し丸めることによって解を求める手法)を用いている.また,Iterative Rounding法のその他の問題への適用や,線形計画アルゴリズムを利用しない組合せ的なアルゴリズムの実現の可能性について検討中である.