Computational Models and Efficient Algorithm Design for Discrete Optimization Problems

离散优化问题的计算模型和高效算法设计

• 批准号: 23500020
• 负责人: MIYANO Eiji
• 金额: $ 3.33万
• 依托单位: Kyushu Institute of Technology
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Scientific Research (C)
• 财政年份: 2011
• 资助国家: 日本
• 起止时间: 2011 至 2013
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-23500020/
• 关键词: 離散最適化問題; オフライン計算モデル; オンライン計算モデル; 計算困難問題; 近似精度; 競合精度; アルゴリズム設計; オフライン最適化問題; 近似アルゴリズム; 近似不可能性; 正則誘導連結部分グラフ抽出問題; ブックマーク最適化問題; シュタイナー木埋め込み最適化問題; 近似困難性; グラフ有向化最適化問題; ソーティングバッファ最適化問題; NP困難問題; 直径を制約とした最適部分グラフ抽出問題; オンライン最適化問題; OVSF符号割当最適化問題

Many interesting discrete optimization problems are computationally intractable (NP-Hard), i.e., there are no algorithms to find optimal solutions to such problems in polynomial time. In some situations, the complete input is not known in advance, for example, the input is a request sequence that is revealed gradually over time. Under the lack of information on future requests, the algorithm has to perform well. In this research, for such two types of "hard" discrete optimization problems, we designed efficient algorithms which are theoretically evaluated by the worst case possible relative errors over all possible instances of the problems.

许多有趣的离散优化问题在计算上是难以解决的（NP-Hard），也就是说，没有算法可以在多项式时间内找到这类问题的最优解。在某些情况下，完整的输入是事先不知道的，例如，输入是一个请求序列，随着时间的推移逐渐显示。在缺乏未来请求信息的情况下，算法必须表现良好。在这项研究中，对于这两种类型的“硬”离散优化问题，我们设计了有效的算法，理论上通过所有可能的问题实例的最坏情况可能相对误差进行评估。

项目成果

弦2部グラフにおける正則誘導部分グラフ探索問題

弦二分图中正则诱导子图搜索问题

• 发表时间: 2014
• 作者: Yosuke Sato;Shutaro Inoue;Akira Suzuki;Katsusuke Nabeshima & Ko Sakai;Yutaka Miyazaki;M. Ito;江藤宏
• 通讯作者: 江藤宏

弦グラフにおける最大正則誘導部分グラフ探索問題

弦图中最大全纯诱导子图搜索问题

• 发表时间: 2013
• 作者: Umair F. Siddiqi;Yoichi Shiraishi and Kazuhiro Motegi;江藤宏
• 通讯作者: 江藤宏

追跡問題に対する進化アルゴリズムの提案

提出一种用于跟踪问题的进化算法

• 发表时间: 2013
• 作者: Umair Siddiqi;Yoichi Shiraishi;Shuji Takahashi and Sadiq Sait;田原慶輔
• 通讯作者: 田原慶輔

弦グラフにおける最大正則誘導部分グラフ探索問題の多項式時間アルゴリズム

弦图中最大全纯诱导子图搜索问题的多项式时间算法

• 发表时间: 2013
• 作者: Taku Kuribayashi;Yasuhito Asano;Masatoshi Yoshikawa;Yutaka Miyazaki;江藤宏
• 通讯作者: 江藤宏

資源増加を許したOVSF 符号割当問題に対する1+ε競合アルゴリズム

允许资源增加的OVSF代码分配问题的1+ε竞争算法

• 发表时间: 2011
• 作者: 高田 祥;鵜川 始陽;中野 圭介;岩崎 英哉;朝廣雄一
• 通讯作者: 朝廣雄一