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

高性能近似アルゴリズムの設計法に関する研究

高性能逼近算法设计方法研究

基本信息

批准号：
16092211
负责人：
平田富夫
金额：
$ 9.86万
依托单位：
Nagoya University
依托单位国家：
日本
项目类别：
Grant-in-Aid for Scientific Research on Priority Areas
财政年份：
2004
资助国家：
日本
起止时间：
2004 至 2007
项目状态：
已结题

项目摘要

グラフ問題や組合せ問題のような離散構造をもつ問題のほとんどはNP完全(最適化問題の場合はNP困難という)であり,現在の計算機では計算時間が膨大になり手に負えない問題である.しかし,たとえNP困難であっても,計算機を用いてなんとか解かなければならない離散最適化問題が情報処理の現場ではますます増えている.たとえば,ORの分野では,より大規模なネットワーク上での資源割当て問題やスケジューリング問題を解かなければならない.また,人工知能の分野では推論処理のような高度な計算を要求する問題がつぎつぎと発生している.このような現実を踏まえ,たとえ求まる解が最適ではなくとも,それに十分近いことを保証できる近似アルゴリズムの設計論が今日の重要な研究テーマとなっている.本研究では、グラフの彩色問題と集合被覆問題を中心とした代表的離散最適化問題に対する高性能近似アルゴリズムを開発するとともに,これまでに提案されている近似アルゴリズムを設計手法の立場から調査・分類し一般的設計法を構築する.今年度の研究成果は以下のようである.最小重み木状被覆問題と頂点彩色問題に対して近似アルゴリズムを設計した.また重みつき集合被覆問題及び集合多重被覆問題に関して成果を得た.この他,センサーネットワークのプロトコルや無線ネットワークの初期化アルゴリズムについて研究を行った.

The problem is NP-complete (NP difficult in optimization cases), and now the computer is computing time is expanding. Computer applications for discrete optimization problems in the field of information processing The problem of resource allocation in large-scale enterprises is solved by solving the problem of resource allocation in large-scale enterprises. The problem of artificial knowledge separation and inference processing and calculation of height requirements arises from time to time. The design theory of this paper is important for today's research. In this paper, we propose a new approach to the design of discrete optimization problems, such as color problems and set coverage problems. This year's research results are as follows. Minimum Weight Wood Cover Problem and Vertex Color Problem The results of the set covering problem and the set multiple covering problem are obtained. In this regard, the initial phase of the development of the wireless network is under study.

项目成果

期刊论文数量（26）

专著数量（0）

科研奖励数量（0）

会议论文数量（0）

专利数量（0）

データ構造の基礎

数据结构基础知识

DOI：
发表时间：
2007
期刊：
影响因子：
0
作者：
安達;蒲生;平田;平田富夫
通讯作者：
平田富夫

A Vector Assignment Approach for the Graph Coloring Problem

图着色问题的向量分配方法

DOI：
发表时间：
2008
期刊：
Lecture Notes in Computer Science (印刷中)
影响因子：
0
作者：
T. Ono;M. Yagiura;T. Hirata
通讯作者：
T. Hirata

An Improved Algorithm for the Nearly Equitable Edge-Coloring Problem

DOI：
发表时间：
2004-05
期刊：
IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences
影响因子：
0
作者：
X. Xie;Takao Ono;Shin-Ichi Nakano;T. Hirata
通讯作者：
X. Xie;Takao Ono;Shin-Ichi Nakano;T. Hirata

Approximation Algorithms for the Weighted Independent Set Problem

加权独立集问题的近似算法