整数最小極大フローに対するアルゴリズム

• 吉永 康

• 施 建明

書誌事項

タイトル別名

• An Algorithm for Minimum Maximal Network Flow

抄録

ネットワークにおける最大流問題が離散最適化の分野での典型問題でり，幅広い分野への応用性をもつ．しかし，現実世界では，しばしばフローを自由に増減させることができない場合がある．そのとき得られるのは極大流である．最小極大流は，ネットワークにおける非効率性指標の一つと考えられる．最小極大流量値を求める問題を最小極大フロー問題と呼び．本論文ではこれまで提案されたアプローチを基礎とし，最小極大フロー問題を線形計画問題とある種の線形相補性問題に帰着できることを理論的に示し，新たなアルゴリズムを提案する．The maximum flow problem is a typical problem in combinatorial optimization, and has been applied in many fields. The optimal value of maximum flow can be attained only on the assumption that a flow on every edge of the given flow can be freely increased and decreased. However, in the real world this assumption can not be satisfied. The minimum maximal flow indicates how inefficiency of the network being utilized. We theoretically reduce the problem into solving a linear programming problem and a linear complementary problem. Finally, we propose a new algorithm based upon the related existing algorithms.

収録刊行物

• 研究報告数理モデル化と問題解決（MPS）

  研究報告数理モデル化と問題解決（MPS） 2011 (1), 1-6, 2011-09-08

詳細情報

• CRID: 1570291227106980480
• NII論文ID: 110008606631
• NII書誌ID: AN10505667
• 本文言語コード: ja
• データソース種別:
  • CiNii Articles