High-performance approximation algorithms for information-flow control problems on networks

网络信息流控制问题的高性能近似算法

• 批准号: 20500020
• 负责人: ASANO Takao
• 金额: $ 2.91万
• 依托单位: Chuo University
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Scientific Research (C)
• 财政年份: 2008
• 资助国家: 日本
• 起止时间: 2008 至 2010
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-20500020/
• 关键词: アルゴリズム理論; 近似アルゴリズム; ネットワーク; NP-困難; 数理計画法; ラウンディング; 性能保証; フロー; ウェブ情報検索; Web情報検索

Problems arising from information-flow control on networks like the Internet include finding routing paths and scheduling packets at nodes. Thus, they are hard to solve efficiently, and in most practical applications, approximate solutions with performance guarantee are often used. In this project, surveying researches on high performance approximation algorithms for problems arising on networks, we proposed algorithms based on mathematical programming formulation, and included obtained results in books which were published in representative publishers in Japan.

在像互联网这样的网络上，信息流控制所产生的问题包括寻找路由路径和在节点处调度数据包。因此，它们很难有效地求解，并且在大多数实际应用中，通常使用具有性能保证的近似解。在这个项目中，调查研究的高性能近似算法的网络上出现的问题，我们提出了基于数学规划公式的算法，并包括在日本的代表性出版商出版的书籍中获得的结果。

项目成果

情報数学(組合せと整数およびアルゴリズム解析の数学)

信息数学（组合与整数数学及算法分析）

• 发表时间: 2009
• 作者: 佐藤康成;他;浅野孝夫
• 通讯作者: 浅野孝夫

情報数学:組合せと整数およびアルゴリズム解析の数学

信息数学：组合数学、整数数学及算法分析

• 发表时间: 2009
• 作者: A.Comuta;M.Kawazoe;T. Takahashi;浅野孝夫
• 通讯作者: 浅野孝夫

アルゴリズムデザイン(J. Kleinberg and E. Tardos, Addison-Wesley, Algorithm Design, 2005、838の日本語訳)

算法设计（J. Kleinberg 和 E. Tardos 的日文翻译，Addison-Wesley，算法设计，2005 年，838）

• 发表时间: 2008
• 作者: 浅野孝夫;浅野泰仁;小野孝男;平田富夫
• 通讯作者: 平田富夫

ホームページ等。

主页等

離散数学(グラフ・束・デザイン・離散確率)

离散数学（图、束、设计、离散概率）

• 发表时间: 2010
• 作者: Putra A.C.;et al.;浅野孝夫
• 通讯作者: 浅野孝夫