Automated Competitive Analysis and Computer-Aided Development Systems for Online Algorithms

在线算法的自动竞争分析和计算机辅助开发系统

• 批准号: 23700001
• 负责人: KAWAHARA Jun
• 金额: $ 2.41万
• 依托单位: Nara Institute of Science and Technology (2012-2013)Hokkaido University (2011)
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Young Scientists (B)
• 财政年份: 2011
• 资助国家: 日本
• 起止时间: 2011 至 2013
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-23700001/
• 关键词: オンラインアルゴリズム; 競合比解析; 自動解析; kフレーム転送量最大化; アルゴリズム; オンライン問題; ユニットクラスタリング; フレーム転送量最大化

For analyzing algorithms for online problems, which model situations without knowledge of the future, a great number of case divisions are needed in order to obtain better solutions. It is practically difficult to perform such case divisions by hand. In this research, an automated analysis technique and computer-aided development systems for online algorithms are proposed. Online algorithms for the k-frame throughput maximization problem and the online clustering problem are designed and analyzed.

对于在线问题的分析算法，其模型的情况下，没有未来的知识，大量的情况下，部门需要，以获得更好的解决方案。实际上很难手工执行这种情况划分。在本研究中，提出了一种在线算法的自动分析技术和计算机辅助开发系统。设计并分析了k帧吞吐量最大化问题和在线分簇问题的在线算法。

项目成果

Optimal buffer management for 2-frame throughput maximization

• DOI: 10.1016/j.comnet.2015.08.046
• 发表时间: 2013-07
• 作者: J. Kawahara;Koji M. Kobayashi

Better bounds for online k-frame throughput maximization in network switches

• DOI: 10.1016/j.tcs.2016.10.009
• 发表时间: 2013-09
• 期刊: Theor. Comput. Sci.
• 作者: J. Kawahara;Koji M. Kobayashi;S. Miyazaki