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) 给定一个边加权二部图和一组初始匹配边，考虑在给定可改变的匹配边的上限的情况下尽可能最大化边权重之和的问题。我们在第 75 届九州电气信息工程师分会联合会会议（2022 年度）上宣布，可以设计一种改进传统近似算法的算法。 (2) 给定两个字符串，可以在多项式时间内找到这两个字符串共有的最长子串。关于嵌入最长公共子串问题，在给定可以添加到输入字符串的一组字符的情况下，使用此作为初始公共子串并添加字符以使公共子串尽可能长。我们利用类似问题和多项式时间差内的等价性提出了指数时间精确算法。该研究成果在第33届组合模式匹配年度研讨会（CPM 2022）上公布。

项目成果

Improved approximation algorithms for non-preemptive multiprocessor scheduling with testing

通过测试改进非抢占式多处理器调度的近似算法

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

University of Alberta(カナダ)

阿尔伯塔大学（加拿大）

Parameterized algorithms for the Happy Set problem

Happy Set 问题的参数化算法

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

変更数制約付き2部グラフ問題の近似アルゴリズム

具有变化次数约束的二分图问题的逼近算法

• 发表时间: 2022
• 作者: 中村裕貴;宮野英次
• 通讯作者: 宮野英次

Approximability of the Distance Independent Set Problem on Regular Graphs and Planar Graphs

正则图和平面图上距离独立集问题的逼近

• DOI: 10.1587/transfun.2021dmp0017
• 发表时间: 2022
• 作者: Hiroshi Eto; Takehiro Ito; Zhilong Liu; Eiji Miyano
• 通讯作者: Eiji Miyano