2段階転送コストを持つ, パス構造ネットワークでの最適なfile transferの構成について(III)

概要

論文の詳細を見る
ファイル複製ネットワークN上の最適なfile transferを求める問題とは, ある情報ファイルのコピーを, 幾つかの点から各点に需要値分の部数だけ, 最小総コストで提供する方法を考えることである.一般的なNに対して, 本問題はNP困難であるが, 多項式時間のアルゴリズムで最適なfile transferが求められるような特殊なNのクラスも知られている.これまで扱ってきたNにおいては, 各点間の転送コストが線形であるという条件があった.実用的な問題を考えると, 転送コストが階段である場合も無視できない.もちろん, このような問題も本質的にNP困難であることが証明されている.しかし, 線形の場合が本質的に木の構成問題に帰着されるのに対して, 階段状の場合はそれほど容易ではなく得体が知れない.本報告では, 構造がパスグラフであり, 各点の需要値が全て1であり, 転送(枝)コストが2段階であるものに限定して考える.これまでの考察の補完を行って, 最適なfile transferを求めるためのO(n^2)のアルゴリズム(nは点の総数)を提案する.
社団法人電子情報通信学会の論文
2000-01-20