サイズ制約付き極小部分集合列挙問題に対する多項式遅延近似列挙アルゴリズムの研究

规模受限最小子集枚举问题的多项式延迟近似枚举算法研究

• 批准号: 21K17812
• 负责人: 栗田 和宏
• 金额: $ 3.08万
• 依托单位: Nagoya University (2022)National Institute of Informatics (2021)
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Early-Career Scientists
• 财政年份: 2021
• 资助国家: 日本
• 起止时间: 2021-04-01 至 2025-03-31
• 项目状态: 未结题
• 来源: https://kaken.nii.ac.jp/en/grant/KAKENHI-PROJECT-21K17812/
• 关键词: 近似列挙; 多項式遅延列挙; サイズ制約

本研究では極小部分グラフ列挙において，極小性とサイズ制約を同時に扱う列挙問題に対し，効率良いアルゴリズムを開発することである．このような問題に対するこれまでのアプローチの一つとして拡張問題を解くというアプローチがあった．拡張問題とはある要素を含み，ある要素を含まない解が存在するかどうかを判定するYes/No問題であり，この問題を解くアルゴリズムと最適化，もしくは近似アルゴリズムを組み合わせることで小さな極小解を列挙することができる．しかし，近年の研究により，この拡張問題は大抵NP完全であることがわかってきた．そのため，このアプローチでの本研究で扱う問題を効率よく解くことは容易ではない．そこで，本研究ではもう一つの列挙アルゴリズムの構築技法である解グラフ技法に基づいたアプローチをおこなっている．このアプローチでは解同士に隣接関係を定義することでできた巨大な隣接関係のグラフを探索することで解を列挙する技法である．これまでの列挙アルゴリズムの構築において，この技法では定義されるグラフの強連結性にしか着目してこなかった．しかし，良い隣接関係を定義することで，小さい解と小さい解をつなぐ有向パスには小さな解しか含まれないように有向グラフを定義できることがわかった．この知見から，いくつかの列挙問題に対し，サイズ制約と極小性を近似的に満たしながら列挙するアルゴリズムを構築できることがわかった．さらに，今年度の研究において，極小な部分集合の列挙だけでなく，いくつかの極大な部分集合に関してもこのような有向グラフの定義ができることがわかった．証明の詳細にはなるが，今回の技法において極大で大きな解の列挙と極小で小さな解の列挙は大きく性質が異なる．そのため，極小解の列挙に使った技法は極大解については単純には適用できない．そのため，極大解に対してこのような技法を開発することも興味深い研究課題である．

本研究的目的是开发一种有效的枚举问题算法，同时处理最小子图枚举中的极小性和大小约束。解决此类问题的方法之一是解决扩展问题。扩展问题是一个是/否问题，确定是否存在包含某个元素但不包含某个元素的解，并且通过将解决该问题的算法与优化相结合，可以找到小的最小解或近似算法。然而，最近的研究表明，这个扩展问题大多是 NP 完全问题。因此，使用这种方法有效地解决本研究中涉及的问题并不容易。因此，本研究使用基于解图技术的方法，这是构建枚举算法的另一种技术。这种方法是一种通过搜索通过定义解决方案之间的邻接关系创建的巨大邻接图来枚举解决方案的技术。到目前为止，在构建枚举算法时，该技术仅关注已定义图的强连通性。然而，我们发现通过定义良好的邻接关系，我们可以定义一个有向图，使得连接小解的有向路径仅包含小解。根据这些知识，我们发现可以构造一种算法来枚举一些枚举问题，同时近似满足大小约束和极小性。此外，在今年的研究中，我们发现不仅可以定义这样的有向图来枚举最小子集，还可以定义几个最大子集。至于证明的细节，在该技术中，最大和大解的枚举与最小和小解的枚举具有非常不同的性质。因此，用于枚举最小解的技术不能简单地应用于最大解。因此，开发这种最大解决方案的技术也是一个有趣的研究课题。

项目成果

連結な極小辺支配集合の近似的なトップ-K列挙

连接最小边支配集的近似 top-K 枚举

• 发表时间: 2022
• 作者: Tesshu Hanaka;Yasuaki Kobayashi;Kazuhiro Kurita;See Woo Lee;Yota Otachi;栗田 和宏;栗田 和宏;栗田 和宏
• 通讯作者: 栗田 和宏

Linear-Delay Enumeration for Minimal Steiner Problems

最小 Steiner 问题的线性延迟枚举

• DOI: 10.1145/3517804.3524148
• 发表时间: 2022
• 期刊: PODS '22: Proceedings of the 41st ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems
• 作者: Kobayashi Yasuaki;Kurita Kazuhiro;Wasa Kunihiro
• 通讯作者: Wasa Kunihiro

マトロイドマッチングとマトロイド交叉上の独立集合に対する効率良い列挙

拟阵交叉上独立集的拟阵匹配和高效枚举

• 发表时间: 2021
• 作者: Tesshu Hanaka;Yasuaki Kobayashi;Kazuhiro Kurita;See Woo Lee;Yota Otachi;栗田 和宏;栗田 和宏;栗田 和宏;栗田 和宏;栗田 和宏;栗田 和宏
• 通讯作者: 栗田 和宏

Polynomial-Delay and Polynomial-Space Enumeration of Large Maximal Matchings

大最大匹配的多项式延迟和多项式空间枚举

• DOI: 10.1007/978-3-031-15914-5_25
• 发表时间: 2022
• 期刊: 48TH INTERNATIONAL WORKSHOP ON GRAPH-THEORETIC CONCEPTS IN COMPUTER SCIENCE
• 作者: Kobayashi Yasuaki;Kurita Kazuhiro;Wasa Kunihiro
• 通讯作者: Wasa Kunihiro

省メモリなトップK列挙アルゴリズムの設計技法

节省内存的top-K枚举算法的设计技术

• 发表时间: 2021
• 作者: Tesshu Hanaka;Yasuaki Kobayashi;Kazuhiro Kurita;See Woo Lee;Yota Otachi;栗田 和宏;栗田 和宏;栗田 和宏;栗田 和宏;栗田 和宏
• 通讯作者: 栗田 和宏