制約充足問題の遷移問題に対する普遍代数学を用いたアプローチ

一种使用通用代数解决约束满足问题中的转移问题的方法

基本信息

批准号：
21K17700
负责人：
木村慧
金额：
$ 3万
依托单位：
Kyushu University
依托单位国家：
日本
项目类别：
Grant-in-Aid for Early-Career Scientists
财政年份：
2021
资助国家：
日本
起止时间：
2021-04-01 至 2026-03-31
项目状态：
未结题

项目摘要

本研究では，制約充足問題の遷移問題の計算複雑さを，普遍代数学を援用することにより分類することを目指している．そのための足掛かりとして，本年度は，制約充足問題の部分クラスである彩色問題の遷移問題を扱った．特に，遷移問題ならではの性質を調査するため，遷移制約をもつ彩色遷移を考え，遷移制約に基づくアルゴリズム開発を行った．本成果に関して執筆した原稿は，アルゴリズムについての国際会議であるThe 33rd International Symposium on Algorithm and Computationに採択され，韓国ソウルにて発表を行った．この成果により得た知見を，制約充足問題の遷移問題の計算複雑さ分類へ生かす予定である．また，昨年度に行った，制約充足問題の特殊例とみなすことのできる整数計画問題に対する特殊な代数的性質をもつ問題における解空間の構造の解析をさらに推し進めた．具体的には，整数解を求める問題を，実数解を求める問題へ緩和した際に，緩和した問題の解から整数解を求める手法を開発していたが，この成果に関して執筆した原稿は組合せ最適化についての国際会議であるThe 7th International Symposium on Combinatorial Optimizationに採択され，オンラインにて発表を行った．さらに，制約充足問題の遷移問題の計算複雑さ分類に関する知見を深めるため，個別の問題に対する計算複雑さ解析やアルゴリズム開発を進めており，結果がまとまってきているところである．また，遷移問題における帰着を考える上で基礎となる観察を行い，遷移問題に対する理解が深まってきている．

这项研究旨在通过纳入通用代数来对过渡问题中过渡问题的计算复杂性进行分类。作为此的垫脚石，今年我们处理着着色问题的过渡问题，这是一类限制满意度问题。特别是，为了研究过渡问题所特有的属性，我们考虑了具有过渡约束的着色过渡，并根据过渡约束制定了算法。关于该结果的手稿是在第33届国际算法和计算国际算法会议上的国际算法上选择的，并在韩国首尔举行。通过此结果获得的发现将用于对过渡问题的计算复杂性和约束满意度问题进行分类。我们还进一步对解决方案空间的结构进行了进一步的分析，这些问题具有特殊的代数属性，用于整数编程问题，这些问题可以被视为我们去年我们进行的约束 - 满足问题的特殊情况。具体而言，当我们放松需要整数解决方案的问题需要真正解决方案的问题时，我们开发了一种方法来找到从解决方案到已放松的解决方案的整数解决方案。我写的关于这一结果的手稿是由第七届国际组合优化国际研讨会（国际组合优化会议）通过的，并在线介绍。此外，为了加深我们对与约束 - 满足问题的过渡问题的计算复杂性分类的了解，我们目前正在研究计算复杂性分析和个人问题的算法开发，并且结果正在汇编。此外，考虑到过渡问题的回归以及对过渡问题的理解，已经进行了基本观察。