Studies on Upper and Lower Approximation Bounds for Graph Optimization Problems

图优化问题的上下近似界研究

• 批准号: 20500017
• 负责人: MIYANO Eiji
• 金额: $ 2.91万
• 依托单位: Kyushu Institute of Technology
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Scientific Research (C)
• 财政年份: 2008
• 资助国家: 日本
• 起止时间: 2008 至 2010
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-20500017/
• 关键词: グラフ最適化問題; 計算複雑さ; 近似上界; 近似下界; 直径d部分グラフ最大化問題; 歪み最小化問題; 最大頂点支配問題; 最大辺支配問題; NP困難問題; アルゴリズム; 最小出次数最大化問題; 弦グラフ; k部グラフ; カクタスグラフ; 強NP困難; ソーティングバッファ問題; メトリックスペース; 一様メトリック; マンハッタンネットワーク; 直径; 部分グラフ

In this research, for many NP-hard graph optimization problems, we designed approximation algorithms, which run in polynomial time and are mathematically evaluated by the worst case possible relative errors over all possible instances of the problems. Also, we showed the lower bounds on approximability for NP-hard graph optimization problems. The inapproximability results demonstrate that unless NP=P we cannot guarantee to do substantially better in polynomial time.

在这项研究中，对于许多NP-难图优化问题，我们设计了近似算法，这些算法在多项式时间内运行，并通过问题的所有可能实例上的最坏情况可能的相对误差进行数学评估。此外，我们还给出了NP-困难图优化问题的可逼近性下界。不可近似性的结果表明，除非NP=P，否则我们不能保证在多项式时间内做得更好。

项目成果

ブロードバンドスケジューリングに対するFIFOアルゴリズム

宽带调度的先进先出算法

• 发表时间: 2008
• 作者: 詰光;将也
• 通讯作者: 将也

最小マンハッタンネットワーク問題に対する2近似アルゴリズム

最小曼哈顿网络问题的 2 逼近算法

• 发表时间: 2008
• 作者: 山崎;康行
• 通讯作者: 康行

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

资源增加的OVSF代码分配问题的两次竞争算法

• 发表时间: 2011
• 作者: S.Yamashita;S.Minato;D.M.Miller;朝廣雄一
• 通讯作者: 朝廣雄一

Drawing Borders Efficiently

有效地绘制边界

• 发表时间: 2007
• 作者: K. Iwama;E. Miyano;H. Ono
• 通讯作者: H. Ono

Approximating Maximum Diameter-Bounded Subgraphs

近似最大直径有界子图

• 发表时间: 2010
• 期刊: Proc.The 9^<th> Latin American Theoretical Informatics Symposium
• 作者: Asahiro;Yuichi
• 通讯作者: Yuichi