離散システムの分解手法の通信網管理への応用

离散系统分解方法在通信网络管理中的应用

• 批准号: 07750084
• 负责人: 岩田 覚
• 金额: $ 0.58万
• 依托单位: Kyoto University
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Encouragement of Young Scientists (A)
• 财政年份: 1995
• 资助国家: 日本
• 起止时间: 1995 至 无数据
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-07750084/
• 关键词: 離散システム; 通信網; グラフ; ネットワーク; 劣モジュラ関数; 数理計画法; オペレーションズ・リサーチ; 組合せ最適化

本研究は,大規模な通信網の管理のために実際問題として解くことが要求されるが,効率的な解法は望めないような最適化問題に対して,近似解や下界値といった有用な情報を得るために,劣モジュラ関数や基本分割に関する理論的な成果を活用する手法の開発を目的としていた.特に,交換機等の設備の更改に関する投資計画に関連して,交換機とその利用者との関係についての膨大なデータの構造を的確に把握するために,基本分割を利用した手法を開発した.この手法を計算機上で実現し,実際的なデータによってその有用性を実験的に確認した.また,離散システムの分解手法そのものに関しては,基本構造と基本分割との間の関係に,マトロイドにおける強射の劣モジュラシステムへの拡張が重要な役割を果たしていることが明らかになった.さらに,劣モジュラシステムの強射系列に関する算法の高速化に成功した.

这项研究旨在开发一种利用supporular函数和基本分区的理论结果的方法，以获取有用的信息，例如近似解决方案和需要大规模通信网络管理的优化问题的下限值，但对于这些问题，无法为此提供有效的解决方案，以便获得有用的有用信息，例如近似的解决方案和近似界值。特别是，关于续订设备的投资计划，我们开发了一种利用基本分区来准确掌握有关交换与用户之间关系的大量数据的结构的方法。该方法是在计算机上实现的，并使用实际数据实验确认了其实用性。此外，关于离散系统本身的分解方法，揭示了强烈火的扩展，在基本结构和基本分区之间的关系中起着重要作用。此外，我们成功地加速了计算方法，用于下方模块化系统的强驱动序列。

项目成果

S. Iwata & K. Murota: "A Mimimax Thorem and a Dulmage-Mendelsohn Type Decomposition for a Class of G Pthatrices" SIAM J. Matrix Anal. Appl.16. 719-734 (1995)

岩田南

M. Shigeno & S. Iwata: "A Dual Approximation Approach to Weighted Matroid Intersection" Oper. Res. Lett.18. 153-156 (1995)

M·重野

S. Iwata: "Principal Structure of Submodular Systems and Hithcock-type Independent Flou" Combinatorica. 15. 515-532 (1995)

S. Iwata：“子模系统的主要结构和 Hithcock 型独立 Flou”Combinatorica。

S. Iwata & K. Murota: "A Theorem on the Principal Stercture for Independent Matchings" Discrete Appl. Math.61. 229-244 (1995)

岩田南