変移する要素間の関係を条件とする組合せ最適化モデル

以变化元素之间的关系为条件的组合优化模型

基本信息

批准号：
16092223
负责人：
宮野英次
金额：
$ 8.38万
依托单位：
Kyushu Institute of Technology
依托单位国家：
日本
项目类别：
Grant-in-Aid for Scientific Research on Priority Areas
财政年份：
2004
资助国家：
日本
起止时间：
2004 至 2007
项目状态：
已结题

项目摘要

本研究では,入力要素の値が時間とともに連続的に変移する環境において,要素間の関係が時々刻々と変化するような様々な問題を扱い,数理最適化モデルとして定式化する統一的な手法の検討と,精度の高い近似解及び高速性能を保証するアルゴリズムの開発を目的とする.今年度は,次のような組合せ最適化モデルの形式化および計算量に関する検討を行った.1.WWWは,ウェブページとハイパーリンクから構成されており,ユーザーはハイパーリンクをクリックして次々にウェブページを表示しながらインターネット上を巡回して,目的のページに辿り着く.希望するウェブページへのアクセスを改善するための自然な解決方法は,ブックマークと呼ばれるショートカットリンクを追加することによりリンク構造を変更していくことである.本問題はブックマーク最適化問題として知られているが,近似可能性および近似不可能性に関する結果は示されていなかった.本研究課題においては,近似比(1-1/e)を持つ多項式時間アルゴリズムが存在すること,入力サイズをNとするとき,NP⊆DTIME(N^o(loglogN))でないという仮定の下で,(1-1/e)よりも良い近似比を持つ多項式時間アルゴリズムが存在しないこと,δをある小さな正定数とするとき,より弱いP=NPでないという仮定の下で,(1-δ)よりも良い近似比を持つ多項式時間アルゴリズムは存在しないということを示した.2.仕事の要求列とその要求列の一部を一時的に保存できるソーティングバッファが与えられた時,要求列の一部を置換することにより仕事効率を上げることを目的としたソーティングバッファ最適化問題について,オンラインモデルに対するFIFOアルゴリズムの競合比の上限と,オフラインモデルの計算複雑さを示した.

在这项研究中，在一个环境中，输入元素的价值随时间不断变化，该格式涉及各种问题，其中元素之间的关系偶尔和偶尔会变化，并将公式作为数学优化模型为了开发一种算法，可以保证今年的高精度和高速度性能，我们检查了以下组合的形式化和计算。一个接一个，并访问所需的网页。，当有近似值率（1-1/e）的多边时间算法，并且当输入大小为n，np⊆dimeTime（n） ^o（loglogn）时）。没有（1-1/e）的多边时间算法，而不是（1-1/e），当δ是一个较小的正数时，它的p = np较弱。没有比（1-δ）.2.2的多边时间算法。在线模型的竞争和离线模型的计算显示了复杂性。

项目成果

期刊论文数量（59）

专著数量（0）

科研奖励数量（0）

会议论文数量（0）

专利数量（0）

Tiling Problems with the Edge-Overwriting Rule

边缘覆盖规则的平铺问题

DOI：
发表时间：
2004
期刊：
情報処理学会研究報告 2004・101
影响因子：
0
作者：
Iwama;Kazuo
通讯作者：
Kazuo

Hardness of Pickup and Delivery for Moving Objects on Broken Lines

折线上移动物体的拾取和传送硬度

DOI：
发表时间：
2005
期刊：
電子情報通信学会技術報告 105・72
影响因子：
0
作者：
Asahiro;Yuichi
通讯作者：
Yuichi

試問予定表作成問題の制約付きモデルに対するNP困難性

考试安排创建问题的约束模型的 NP 难度

DOI：
发表时间：
2007
期刊：
影响因子：
0
作者：
清成;悠貴
通讯作者：
悠貴

Approximability and Non-approximability of the Minimum Block Transfer Problem

最小块传输问题的逼近性和非逼近性

DOI：
发表时间：
2006
期刊：
電子情報通信学会技術報告 105・679
影响因子：
0
作者：
Asahiro;Yuichi
通讯作者：
Yuichi

テストデータ評価を用いた新しい遺伝的アルゴリズムによるバンプ探索法

使用新遗传算法的凹凸搜索方法使用测试数据评估

DOI：
发表时间：
2008
期刊：
影响因子：
0
作者：
廣瀬;行實
通讯作者：
行實

DOI：
{{ item.doi }}
发表时间：
{{ item.publish_year }}
期刊：
{{ item.journal_name }}
影响因子：
{{ item.factor }}
作者：
{{ item.authors }}
通讯作者：
{{ item.author }}

数据更新时间：{{ journalArticles.updateTime }}

作者：
{{ item.author }}

数据更新时间：{{ monograph.updateTime }}

作者：
{{ item.author }}

数据更新时间：{{ sciAawards.updateTime }}

作者：
{{ item.author }}

数据更新时间：{{ conferencePapers.updateTime }}

作者：
{{ item.author }}

数据更新时间：{{ patent.updateTime }}

宮野英次其他文献

最大・最小支配ツアー問題の計算複雑さ

最大-最小支配旅游问题的计算复杂度

DOI：
发表时间：
2018
期刊：
影响因子：
0
作者：
朝廣雄一;Guohui Lin;Zhilong Liu;宮野英次;小林賢也，Guohui Lin，宮野英次，八木田剛;寺原一平，江藤宏，Guohui Lin，宮野英次;歌島侃勇，朝廣雄一，Jesper Janssen，Guohui Lin，宮野英次，小野廣隆;林田将敬，宮野英次;吉瀬紘平，宮野英次;税所航平，宮野英次;歌島侃勇，朝廣雄一，Jesper Janssen，Guohui Lin，宮野英次，小野廣隆;寺原一平，朝廣雄一，江藤宏，土中哲秀，Guohui Lin，宮野英次;小林賢也，Guohui Lin，宮野英次，八木田剛;朝廣雄一，ジャンソンジェスパー，宮野英次，小野廣隆，T.P.サディヤ;朝廣雄一，ジャンソンジェスパー，宮野英次，ニクパイヘサム，小野廣隆;江藤宏，土中哲秀，宮野英次，西島歩美，小野廣隆，大舘陽太，斎藤寿樹，上原隆平，ヴァンデルザンデントム;八木田剛，朝廣雄一，宮野英次;野々上夏葵，江藤宏，宮野英次
通讯作者：
野々上夏葵，江藤宏，宮野英次

重複無し最長共通部分列問題の計算時間

无重复的最长公共子序列问题的计算时间

DOI：
发表时间：
2019
期刊：
影响因子：
0
作者：
朝廣雄一;Guohui Lin;Zhilong Liu;宮野英次;小林賢也，Guohui Lin，宮野英次，八木田剛;寺原一平，江藤宏，Guohui Lin，宮野英次;歌島侃勇，朝廣雄一，Jesper Janssen，Guohui Lin，宮野英次，小野廣隆;林田将敬，宮野英次;吉瀬紘平，宮野英次;税所航平，宮野英次;歌島侃勇，朝廣雄一，Jesper Janssen，Guohui Lin，宮野英次，小野廣隆
通讯作者：
歌島侃勇，朝廣雄一，Jesper Janssen，Guohui Lin，宮野英次，小野廣隆

最小ブロック転送問題について

关于最小块传输问题

DOI：
发表时间：
2018
期刊：
影响因子：
0
作者：
朝廣雄一;Guohui Lin;Zhilong Liu;宮野英次;小林賢也，Guohui Lin，宮野英次，八木田剛;寺原一平，江藤宏，Guohui Lin，宮野英次;歌島侃勇，朝廣雄一，Jesper Janssen，Guohui Lin，宮野英次，小野廣隆;林田将敬，宮野英次;吉瀬紘平，宮野英次;税所航平，宮野英次;歌島侃勇，朝廣雄一，Jesper Janssen，Guohui Lin，宮野英次，小野廣隆;寺原一平，朝廣雄一，江藤宏，土中哲秀，Guohui Lin，宮野英次;小林賢也，Guohui Lin，宮野英次，八木田剛;朝廣雄一，ジャンソンジェスパー，宮野英次，小野廣隆，T.P.サディヤ;朝廣雄一，ジャンソンジェスパー，宮野英次，ニクパイヘサム，小野廣隆;江藤宏，土中哲秀，宮野英次，西島歩美，小野廣隆，大舘陽太，斎藤寿樹，上原隆平，ヴァンデルザンデントム;八木田剛，朝廣雄一，宮野英次;野々上夏葵，江藤宏，宮野英次;柳植竜，朝廣雄一，Guohui Lin，宮野英次;寺原一平，江藤宏，Guohui Lin，宮野英次;小林賢也，Guohui Lin，宮野英次，斎藤寿樹，鈴木顕，八木田剛;八木田剛，朝廣雄一，宮野英次
通讯作者：
八木田剛，朝廣雄一，宮野英次

C5フリー正則グラフ上での誘導マッチング問題に対する近似アルゴリズム

C5自由正则图引导匹配问题的逼近算法

DOI：
发表时间：
2018
期刊：
影响因子：
0
作者：
朝廣雄一;Guohui Lin;Zhilong Liu;宮野英次;小林賢也，Guohui Lin，宮野英次，八木田剛;寺原一平，江藤宏，Guohui Lin，宮野英次;歌島侃勇，朝廣雄一，Jesper Janssen，Guohui Lin，宮野英次，小野廣隆;林田将敬，宮野英次;吉瀬紘平，宮野英次;税所航平，宮野英次;歌島侃勇，朝廣雄一，Jesper Janssen，Guohui Lin，宮野英次，小野廣隆;寺原一平，朝廣雄一，江藤宏，土中哲秀，Guohui Lin，宮野英次;小林賢也，Guohui Lin，宮野英次，八木田剛;朝廣雄一，ジャンソンジェスパー，宮野英次，小野廣隆，T.P.サディヤ;朝廣雄一，ジャンソンジェスパー，宮野英次，ニクパイヘサム，小野廣隆;江藤宏，土中哲秀，宮野英次，西島歩美，小野廣隆，大舘陽太，斎藤寿樹，上原隆平，ヴァンデルザンデントム;八木田剛，朝廣雄一，宮野英次;野々上夏葵，江藤宏，宮野英次;柳植竜，朝廣雄一，Guohui Lin，宮野英次
通讯作者：
柳植竜，朝廣雄一，Guohui Lin，宮野英次

ネットワークの同種親和性を定式化した最適化問題

制定网络同质性的优化问题

DOI：
发表时间：
2019
期刊：
影响因子：
0
作者：
朝廣雄一;Guohui Lin;Zhilong Liu;宮野英次;小林賢也，Guohui Lin，宮野英次，八木田剛;寺原一平，江藤宏，Guohui Lin，宮野英次;歌島侃勇，朝廣雄一，Jesper Janssen，Guohui Lin，宮野英次，小野廣隆;林田将敬，宮野英次;吉瀬紘平，宮野英次;税所航平，宮野英次;歌島侃勇，朝廣雄一，Jesper Janssen，Guohui Lin，宮野英次，小野廣隆;寺原一平，朝廣雄一，江藤宏，土中哲秀，Guohui Lin，宮野英次
通讯作者：
寺原一平，朝廣雄一，江藤宏，土中哲秀，Guohui Lin，宮野英次