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

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

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

In this paper, we study the minimum number of problems, and the minimum number of problems. The problem is solved by a simple solution to the problem. The problem of expansion contains elements, elements, solutions, existence, determination, Yes/No problem, solutions, optimization, approximation, combination, small solution, column, etc. In recent years, research has been carried out on this problem, which is almost NP complete. This study is about the problem of how to solve it. This study is aimed at exploring the construction techniques of the system. The definition of the adjacent relationship of the same person is discussed. This technique is defined by the strong linkage between the two groups. The definition of good adjacency relation is: small solution, small solution, small solution. This knowledge is not limited to the problem of column structure, but is limited to the problem of minimization. In this year's study, the minimum part of the set is set up, and the maximum part of the set is set up. It is proved that the details of this paper are different from each other, and the techniques of this paper are different from each other.そのため，极小解の列挙に使った技法は极大解については単纯には适用できない. The maximum solution is the development of a deep research topic.

项目成果

連結な極小辺支配集合の近似的なトップ-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;栗田 和宏;栗田 和宏;栗田 和宏;栗田 和宏;栗田 和宏
• 通讯作者: 栗田 和宏