要約■■学生論文賞受賞論文

MinimumCostSourceLocation ProbJemswithFlowRequirements
坂下麻里子（大阪大学大学院基礎t学研究科システム創成専攻 現所属・京都大学大学院情報学研究科数理工学専攻博十後期課程）

指導教員 牧野和久肋教授，乾口雅弘教授

s．t．￠▼（S，〃）≧d￣（〃），￠＋（〃，5）≧d＋（〃）（〃∈V），

1．はじめに

5⊆Ⅴ．

ソース配置問題とは，与えられたネットワークにおただし，￠▼（ズ，y），￠＋（ズ，y）は点集合Xからyいて，フロー（連結度）に基づく制約条件の下で最小への連結度を表す．また，￠￣（S，（〃）），￠＋（（〃），S）をコストを与えるソース集合（配置）を求める問題であそれぞれ簡潔に￠￣（5，ぴ），￠十（ぴ，5）と書く．本論文

る．この間題は，例えば，マルチメディアネットワー

では，￠±として，次の3種類の連結度を考察する．

ク中にサービス要求量を指定した複数のクライアント（i）￠￣（S，〃）＝人（5，〃），￠＋（〃，S）＝ス（〃，S），が与えられたとき，その要求を満足しながら最小コス（ii）￠￣（S，〃）＝方（S，〃），￠＋（〃，5）＝〝（〃，S），トで（ミラー）サーバを配置するという問題をモデル（iii）￠￣（S，〃）＝方￣（S，〃），￠＋（〃，S）＝（方＋（〃，5），化したものであり，信頼度を考慮に入れた施設配置問

ただし，人（ズ，y）は点集合ガからyへの最大フロ題として近年盛んに研究されている（例えば，［1，ー値で，ズny≠￠のときス（ズ，y）＝＋∞とする．

2］）．また，ネットワーク理論で有名な連結度増大問

また，ズ（ガ，y）は方からyへの端点以外の点を共題とも深く関連している．

有しない最大パス数で，ガny≠軋 または，〃∈ガ，

ソース配置問題における制約条件としては，枝連結紺∈yである枝（〃，紺）∈Aが存在するとき，〝（ズ，度，および，点連結度に基づくものがある．枝連結度y）＝＋∞とする．方￣（S，〃），および，ガ＋（〃，S）は，要求はリンク故障に対する信頼度，点連結度要求は点それぞれ点集合Sから点〃，および，〃から5への故障に対する信頼度に対応しており，点連結度要求に〃以外の点を共有しない最大パス数を表し，ぴ∈Sの対しては，ソース故障の存否に関して2種類の要求がときガ▼（S，〃）＝ガ＋（〃，5）＝＋∞とする．（i）は枝連結考察されている．

度，（ii）はソース故障を許さない点連結度，（iiDはソース

本論文では，未解決問題として残されていた，無向故障を許す点連結度を表す．

ネットワーク中の枝連結度に基づくソース配置問題の問題の拡張：＿ヒ記のソース配置問題では，コスト関数

強NP困難性，および，近似困難性を示す．また，として施設の建設費用（〃における建設費用c（〃））のすべてのNP困難な場合に適用可能な精度保証付きみを扱っている．しかしながら，現実的なコスト関数の近似アルゴリズム，木構造ネットワークに対する効として，建設費用に加え，供給量にも依存するものを率的なアルゴリズムを開発する．我々はさらに，コス考察することが求められている．従って，本論文ではト関数として，建設費用に加え，供給量にも依存する

以下のように供給量を考慮したソース配置問題を考察ソース配置問題を考察し，様々な結果を得る．

する．ここでは，頁数制限のため，枝連結度スに対する拡張についてのみ述べる．

2．ソース配置問題とその拡張

ネットワーク〟中のフロー甲：A→R＋が以下の条

点集合Ⅴと枝集合AをもつグラフCに容量関数〟：A→取＋を付与したネットワーク〟＝（G＝（V，件を満たすとき，供給J：Ⅴ→R＋に対して実行可能であると呼ぶ．

A），〟）を考える．ただし，R十は非負実数の集合であ−∬（〃）≦∂甲（〃）≦∬（ぴ）（〃∈V）る．このネットワーク〟，要求関数d￣，d＋：Ⅴ→取，0≦甲（α）≦㍑（α）

（1）

（α∈A）

（2）

コスト関数c：Ⅴ→R＋が与えられたとき，ソース配ただし，∂p（〃）はフロー甲の点〃における境界を示

置問題は以下のように記述できる．

し，∂p（〃）＝∑（〃，∽）∈。甲（ぴ，乙〃）−∑（ぴ，む）∈。P（z〃，ぴ）とMin．∑む∈5C（〃）
2005年12月号

定義される．人▲（J；〃）とバ＋（J；ぴ）をそれぞれ供給J© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

（51）841

における点〃への最大流入量（−∂ダ（〃）＋∬（〃））と〃定理4．木構造ネットワーク〟中の点連結度要求ズ，からの最大流出量（∂甲（〃）＋∬（〃））とする．枝連結度要ガをもつソース配置問題はともに多項式時間で解け求を持つ拡張されたソース配置問題は，ネットワークる．

〟＝（C＝（Ⅴ，A），〟），要求関数d∴d＋：Ⅴ→R．，各［1］の弱NP困難性の結果から，定理3の擬多項式

点〃∈Ⅴにおけるコストを表す単調な凹関数cぴ：R＋時間は計算限界である．また，定理4は，点連結度要→R＋が与えられたとき，以下のように記述できる．

求を持つソース配置問題に対する初めての効率的に計Min．∑む∈yCむ（∬（〃））

算可能な部分クラスを示している．

s．t．ス￣（∬；ぴ）≧d￣（ぴ），ス十（∬；〃）≧d＋（わ（ぴ∈Ⅴ），∬（ぴ）≧0（ぴ∈Ⅴ）．
ここで，（㍍の単調凹性は，ネットワーク設計問題な

4．拡張されたソース配置問題に対する成果

近似アルゴリズム：本論文では，拡張されたソース配どでよく扱われる自然な仮定である．

3．ソース配置問題に対する成果

置問題を劣モジュラ被覆問題として定式化し，食欲アルゴリズムを開発することで，以下の定理を得る．

無向・枝連結度要求をもつ場合の計算困難性：無向ネ定理5．（拡張された）ソース配置問題は，容量，おットワーク中の枝連結度要求（すなわち，￠（＝￠￣＝よび，要求関数が整数である場合，多項式時間で（1￠＋）＝ん d＝d＋（＝d￣））を持つソース配置問題に対し＋1n∑ぴ∈γ（d￣（〃）＋d＋（〃）））−近似可能である．
定理2より，この貪欲アルゴリズムは枝連結度要求て，以下の定理が成立する．
定理1．無向ネットワーク中の枝連結度要求を持つソに対して，（オーダーの意味で）最適である．

ース配置問題は強NP困難である．

無向・一様な枝連結度要求をもつ拡張ソース配置問

これは，［1］で提示されていた未解決問題を解くも題：無向ネットワークにおいて一様な枝連結度要求のである．この定理は，NP困難問題として有名な集（すなわち，d（〃）＝々（〃∈Ⅴ））をもつ拡張されたソース合被覆問題をソース配置問題に帰着させることによっ配置問題をラミナー被覆問題として定式化し，以下のて示される．さらに，我々は，集合被覆問題の近似困定理を得る．

難性，および，帰着のギャップ保存性より以下の定理

定理6．無向ネットワーク中の一様な杖連結度要求をを得る．

持つ拡張されたソース配置問題は，定理2．NP望DTIME（N￣10blogN）ならば，ある定数1．0（乃研＋乃2（仔＋log乃））時間で解ける．

c＞0が存在して，無向ネットワーク中の枝連結度要2．各コスト関数cぴが固定費つき線形関数として記求を持つソース配置問題に対する多項式時間c述できる場合は，0（死（弼＋乃logγ乙））時間で解けln∑托γd（〃）一近似アルゴリズムは存在しない．

る．

ここで，NP宰DTIME（N10g10gN）とは，Nを入力長としたとき，任意のNP完全問題が0（Ⅳ10g10g〃）時3．より一般的なコスト関数（すなわち，Fが一般の凹関数）のとき，計算困難である．

間の決定性アルゴリズムを持たないことを意味し，多くの計算量理論の研究者によって信じられている．また，α−近似アルゴリズムAとは，近似比（すなわち，謝辞 本研究を行うにあたり，多くのご指導を頂きました京都大学の藤垂悟先生に感謝いたします．

（Aの出力する解のコスト値）／（最適値））が必ずα以
参考文献内である解を出力するアルゴリズムのことをいう．
木構造ネットワーク中のソース配置問題：また，与えられたネットワーク〟が木構造であるとき，以下の［1］K．Arata，S．Iwata，K．Makino，S．Fujishige：Locat−

ingsourcestomeetflowdemandsinundirected net−works，j．AhlOYlthms，42（2002），54−68，肯定的な定理が成立する．
定理3．木構造ネットワーク〟において枝連結度要求をもつソース配置問題は，容量関数と要求関数が整［2］M．Bar急sz，J．Becker，A．Frank：Analgorithmfor
sourcelocationin directed graphs，OR Lette7S，33（2005），22ト230．

数のとき，擬多項式時間で解ける．

842（52）© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

オペレーションズ・リサーチ