Hybrid Approaches to Computationally Hard Problems : Approximation, Randomization, and Parallelization

计算难题的混合方法：近似、随机化和并行化

• 批准号: 20500021
• 负责人: CHEN Zhi-zhong
• 金额: $ 1.66万
• 依托单位: Tokyo Denki University
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Scientific Research (C)
• 财政年份: 2008
• 资助国家: 日本
• 起止时间: 2008 至 2011
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-20500021/
• 关键词: 近似アルゴリズム; 確率アルゴリズム; 並列アルゴリズム; NP困難性; 網状ネットワーク問題; RH下界; 最大共通無閉路森問題; 最大共通森問題; バイオインフォマティクス; 固定パラメータアルゴリズム; 整数線形計画問題; 計算生物学; 最適化問題; Closest文字列問題; Tandem複製歴再構築問題; Closest部分列問題; 埋込(l,d)-モティーフ問題; 最大2-辺彩色可能部分グラフ問題; 最大三角形詰め込み問題; 安全マルチキャスト鍵管理問題

Problems that aim to maximize certain kinds of profit or minimize certain kinds of cost are ubiquitous in the real world. Such problems are called optimization problems and most of them are computationally hard. A well-used approach to hard optimization problems is approximation(which aims to find near-optimal solutions efficiently). In this project, we combine this approach with two other powerful approaches(namely, randomization and parallelization) and apply the resulting hybrid approach to several hard optimization problems. As the results, we have obtained more efficient algorithms for the hard problems than the previous bests.

旨在最大化某些利润或最小化某些成本的问题在现实世界中无处不在。这些问题称为优化问题，大多数问题在计算上都很难。解决严格优化问题的良好方法是近似（旨在有效地找到近乎最佳的解决方案）。在这个项目中，我们将这种方法与另外两种强大的方法（即随机化和并行化）相结合，并将结果混合方法应用于几种硬优化问题。作为结果，我们已经获得了与以前的最好问题相比，为硬问题获得了更有效的算法。

项目成果

An Improved Approximation Algorithm for the Capacitated Multicast Tree Routing Problem

• DOI: 10.1007/978-3-540-85097-7_27
• 发表时间: 2008-08
• 作者: Zhipeng Cai;Zhi-Zhong Chen;Guohui Lin;Lusheng Wang

A Fast Exact Algorithm for the Closest Substring Problem and Its Application to the Planted (l, d)-Motif Model

一种快速精确的最近子串问题算法及其在Planted (l, d)-Motif模型中的应用

• 发表时间: 2010
• 作者: 田尻達郎;他;Zhi-Zhong Chen
• 通讯作者: Zhi-Zhong Chen

An Improved Approximation Algorithm for Maximum Edge 2-Coloring in Simple Graphs

简单图中最大边2着色的改进近似算法

• 发表时间: 2008
• 期刊: Journal of Discrete Algorithms 6
• 作者: 辻井;笠原;趙;松尾;Zhi-Zhong Chen
• 通讯作者: Zhi-Zhong Chen

A Linear Kernel for Co-Path/Cycle Packing

• DOI: 10.1007/978-3-642-14355-7_10
• 发表时间: 2010-07
• 作者: Zhi-Zhong Chen;M. Fellows;B. Fu;Haitao Jiang;Yang Liu;Lusheng Wang;B. Zhu

Approximation Algorithms for Reconstructing the Duplication History of Tandem Repeats

重建串联重复重复历史的近似算法

• 发表时间: 2007
• 期刊: Lecture Notes in Computer Science 4598
• 作者: Zhi-Zhong;Chen;T.;Nagoya;Zhi-Zhong Chen;Lusheng Wang
• 通讯作者: Lusheng Wang