一般化最大フロー問題の多項式アルゴリズム

藤重研究室　　野上　裕介

私たちが，現在生活している社会において，インターネットなどによるネットワーク化が盛んに行われている．そのようなネットワーク社会において，いかに損失を少なくデータなどを送るか，いかに速くデータを安全に送るかといったことが重要な問題になってきている．このような要求に答えるために，どのような経路でデータのやりとりを行えばよいのかといった問題に最適な解を与えてくれるのが，一般化最大フロー問題である．そのため，一般化最大フロー問題の重要性がますます大きくなってきている．

一般化最大フロー問題とは，ネットワークの始点と終点の間にできるだけ多くの流量(フロー）を流す問題です．ネットワーク間にはいくつかの点が存在し，それらは枝で結ばれている．枝にはフローを流すことができる限界を示す枝容量や，流れたフローを大きくしたり，小さくしたりするゲインが存在する．点には超過が存在する．フローを流す前の超過を初期超過という．これらのファクタをうまく使って，一般化最大フロー問題を解くアルゴリズムが研究されている．このような研究の背景には，数理計画を研究している人たちが，現在のようなネットワーク社会を意識し，より計算時間の少ないアルゴリズムの開発に力を注いできた結果がある．そのようなアルゴリズムは現在の社会において，とても有益なものとなっている．

本報告では，一般化最大フロー問題を高速に解くアルゴリズムの開発に関する最新の成果をまとめるとともに，手数料を含む一般化最大フロー問題及び凹関数のゲインを持つ一般化最大フロー問題に関する問題提起，モデル化を行い，今後の研究の第一歩としたい．



[PDF File]