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.

诸如Internet之类的网络中的信息流控制引起的问题包括在节点上查找路由路径和调度数据包。因此，它们很难有效地解决，并且在大多数实际应用中，经常使用具有性能保证的近似解决方案。在该项目中，对网络上出现的问题的高性能近似算法进行了调查，我们根据数学编程公式提出了算法，并包括在日本代表出版商发表的书籍中获得的结果。

项目成果

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

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

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

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

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

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

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

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

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

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

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

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

組合せ最適化第2版:理論とアルゴリズム(B. Korte and J.Vygen, Springer, Combinatorial Optimization (4th ed.),2007,697の日本語訳)

组合优化第二版：理论与算法（B. Korte 和 J.Vygen 的日文翻译，Springer，组合优化（第 4 版），2007 年，697）

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