权益分类	功能权益	普通用户	{{item.name}}会员
{{category.name}}	{{benefitItem.name}}

最適化問題の近似アルゴリズムとその並列化

优化问题的逼近算法及其并行化

基本信息

批准号：
08780310
负责人：
陳致中
金额：
$ 0.64万
依托单位：
Tokyo Denki University
依托单位国家：
日本
项目类别：
Grant-in-Aid for Encouragement of Young Scientists (A)
财政年份：
1996
资助国家：
日本
起止时间：
1996 至无数据
项目状态：
已结题

项目摘要

本研究では、2種類の最適化問題を考えた。最初の問題は最大部分グラフ問題(MSPと略す)である。多くの実用的な問題がMSPとして定式化できるが、ほとんどのMSPがNP困難である。そのため、MSPに対する近似アルゴリズムの研究が盛んに行なわれてきた。LiptonとTarjanは、人力を平面グラフに制御した場合のMSPを考え、その場合のMSPを解く一様の近似アルゴリズムを与えた。のちに、Bakerは実用性の面からLiptonとTarjanの近似アルゴリズムを改善し、人力を平面グラフに制限した場合のMSPを解く実用的な一様の近似アルゴリズムを与えた。本研究では、「Bakerの結果の中で要求される入力グラフの平面性は本質的であるのか?」という質問を考え、それに肯定的な答えがあることを証明した。もっと具体的に言えば、入力グラフの平面性という制限をK_<3,3>-freeかまたはK_5-freeに緩めてもMSPを解く実用的な一様の近似アルゴリズムがあることを示した。この結果を得るのに近年盛んに研究ささているtreewidthという概念を用いた。2番目に考えた問題は最短超文字列問題(shortest superstring problem)である。この問題はデータ圧縮とDNAの研究に応用性があるため、今まで盛んに研究されてきた。特に、この問題に対する近似アルゴリズムの研究は最近非常に盛んである。本研究以前に、この問題を解くNC近似アルゴリズムがいくつか既にあった。その中で最もよいのは本研究者によって得られた。本研究では、そのNC近似アルゴリズムの効率を更に改善した。

In this study, 2 kinds of optimization problems were examined. The initial problem is the largest part of the problem (MSP). The problem of multi-application is formulated as MSP and NP difficulty. The study of the relationship between MSP and the author of this paper was carried out in detail. Lipton Tarjan, human plane, control, MSP, etc. In addition to the above, Baker's approach to practical use is to improve the quality of human resources and to limit the application of MSP. This study is based on "Baker's results and requirements". The answer is yes. The specific language, the input force, the planarity, the control limit, the K_<3,3>-free, the K_5-free, the MSP, the solution, the approximation, the solution, the solution, the solution. The result is that the treewidth concept has been studied in recent years. 2. The shortest superstring problem The problem is that DNA research is very useful. The research on this problem has been very successful recently. In this study, the previous problems were solved approximately. The most important thing is that the researchers have been working hard. This study aims to improve the efficiency of NC approximation.