Algorithm Design for k-Constrained Combinatorial Optimization Problems

k约束组合优化问题的算法设计

基本信息

批准号：
21K11755
负责人：
宮野英次
金额：
$ 2.66万
依托单位：
Kyushu Institute of Technology
依托单位国家：
日本
项目类别：
Grant-in-Aid for Scientific Research (C)
财政年份：
2021
资助国家：
日本
起止时间：
2021-04-01 至 2024-03-31
项目状态：
已结题

来源：
https://kaken.nii.ac.jp/en/grant/KAKENHI-PROJECT-21K11755/
关键词：
組合せ最適化問題計算困難性多項式時間近似アルゴリズム指数時間アルゴリズムマッチング問題埋め込み型最長共通部分列問題初期解多項式時間アルゴリズム最小全域木問題最長共通部分列問題 k制約付き組合せ最適化問題計算容易性・困難性固定パラメータ容易アルゴリズム指数時間厳密アルゴリズム

项目摘要

組合せ最適化問題に対する解法アルゴリズムは，与えられた制約条件を満たす実行可能解の中から，目的関数の値を最大または最小にするような解を見つけることが目的となる．従来，最適化問題に対するアルゴリズム設計の際には，制約条件を満たす解をゼロから求めることを仮定しているが，実際の場面では，ある程度の解が既に求められており，その解から始めて，より良い更新解を求めることも多い．本研究では，制約条件に加えて，初期解および初期解からの変更制約が与えられた元での組合せ最適化問題を対象に計算容易性・困難性の解明を目標としている．今年度の主要な研究結果は以下である．(1) 辺重み付き二部グラフと初期のマッチング辺集合が与えられたときに，変更できるマッチング辺の上界が与えられたときに，出来るだけ辺重みの合計が最大となる問題について検討を行った．従来の近似アルゴリズムを改善するアルゴリズムを設計できることを第75回電気・情報関係学会九州支部連合大会(2022年度)において公表した．(2) 2つの文字列が与えられたとき，2つの文字列に共通な部分文字列の中で，最長となる部分文字列は多項式時間で見つけることが出来る．これを初期共通部分文字列として，さらに入力文字列に追加可能な文字集合が与えられたときに，共通部分文字列を出来るだけ長くするように文字追加する埋め込み型の最長共通部分文字列問題について検討を行った．類似問題と多項式時間の差の範囲で等価であることを用いることで指数時間厳密アルゴリズムを提案した．研究成果については33rd Annual Symposium on Combinatorial Pattern Matching (CPM 2022)において公表を行った．

组合优化问题的解决方案算法的目的是找到一种解决方案，该解决方案可以最大化或最小化从满足给定约束的可执行解决方案中目标函数的值。传统上，当设计用于优化问题的算法时，已经假定要从头开始找到满足约束的解决方案，但是在实际情况下，已经需要一定量的解决方案，并且通常以该解决方案开始更好的更新解决方案。在这项研究中，目标是阐明计算易于和难度，针对组合优化问题，在这些问题中，初始解决方案和修改约束是从初始解决方案给出的。今年的主要研究结果如下：（1）我们检查了边缘权重的总和在给出边缘权重时尽可能强大的问题，其中具有初始匹配的边缘集和可以更改的匹配边缘的上限。在电气与信息关系协会（2022）的第75九州分支机构会议上宣布，可以设计改善常规近似算法的算法。（2）给定两个字符串，在多项式时间内可以找到两个字符串的最长子字符串。我们检查了嵌入式类型的最长常见基因弦问题，其中当可以添加到输入字符串中的字符集时，将字符添加到通用子字符串中，以便尽可能长。我们通过使用相似问题和多项式时间之间的等效差异范围，提出了一种指数时间严格的算法。研究结果发表在第33届年度组合模式匹配研讨会上（CPM 2022）。

项目成果

期刊论文数量（36）

专著数量（0）

科研奖励数量（0）

会议论文数量（0）

专利数量（0）

Publication list

DOI：
10.1088/1742-6596/1208/1/011005
发表时间：
2019-05
期刊：
Journal of Physics: Conference Series
影响因子：
0
作者：
Johannes Fürnkranz
通讯作者：
Johannes Fürnkranz

文字列検索を応用した赤道域地磁気変動パターンの簡易検索手法の提案

提出一种利用字符串搜索的赤道地区地磁波动模式的简单搜索方法

DOI：
发表时间：
2021
期刊：
影响因子：
0
作者：
Kato T;Matsubara N;Shiota M;Eto M;Osawa T;Abe T;Shinohara N;Yasumizu Y;Tanaka N;Oya M;Nishimoto K;Hayashi T;Nakayama M;Kojima T;Namikawa K;Fujisawa T;Okano S;Hida E;Nakamura Y;Bando H;Yoshino T;Nonomura N;松山幸生，斎藤寿樹，宮野英次，藤本晶子，吉川顕正，阿部修司
通讯作者：
松山幸生，斎藤寿樹，宮野英次，藤本晶子，吉川顕正，阿部修司

Path Cover Problems with Length Cost

具有长度成本的路径覆盖问题

DOI：
10.1007/978-3-030-96731-4_32
发表时间：
2022
期刊：
Lecture Notes in Computer Science
影响因子：
0
作者：
Kobayashi Kenya;Lin Guohui;Miyano Eiji;Saitoh Toshiki;Suzuki Akira;Utashima Tadatoshi;Yagita Tsuyoshi
通讯作者：
Yagita Tsuyoshi

Improved approximation algorithms for non-preemptive multiprocessor scheduling with testing

DOI：
10.1007/s10878-022-00865-y
发表时间：
2022-05
期刊：
Journal of Combinatorial Optimization
影响因子：
1
作者：
Mingyang Gong;R. Goebel;Guohui Lin;Eiji Miyano
通讯作者：
Mingyang Gong;R. Goebel;Guohui Lin;Eiji Miyano

Parameterized algorithms for the Happy Set problem

Happy Set 问题的参数化算法

DOI：
10.1016/j.dam.2021.07.005
发表时间：
2021
期刊：
Discrete Applied Mathematics
影响因子：
1.1
作者：
Asahiro Yuichi;Eto Hiroshi;Hanaka Tesshu;Lin Guohui;Miyano Eiji;Terabaru Ippei
通讯作者：
Terabaru Ippei

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：
发表时间：
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.サディヤ;朝廣雄一，ジャンソンジェスパー，宮野英次，ニクパイヘサム，小野廣隆;江藤宏，土中哲秀，宮野英次，西島歩美，小野廣隆，大舘陽太，斎藤寿樹，上原隆平，ヴァンデルザンデントム;八木田剛，朝廣雄一，宮野英次;野々上夏葵，江藤宏，宮野英次
通讯作者：
野々上夏葵，江藤宏，宮野英次

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

关于最小块传输问题

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：
发表时间：
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，宮野英次