組合せ的制約をもつ線形システムの解法

求解具有组合约束的线性系统

• 批准号: 17K12646
• 负责人: 澄田 範奈
• 金额: $ 2.41万
• 依托单位: Tokyo Institute of Technology (2020-2022)Tokyo Metropolitan University (2018-2019)National Institute of Informatics (2017)
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Young Scientists (B)
• 财政年份: 2017
• 资助国家: 日本
• 起止时间: 2017-04-01 至 2024-03-31
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/en/grant/KAKENHI-PROJECT-17K12646/
• 关键词: ロバスト最適化; 密グラフ; 確率的解; オンラインマッチング; 線形相補性問題; 公平割当; 線形計画問題; アルゴリズム; マトロイド; 組合せ最適化

本研究の目的は，組合せ的制約をもつ線形システムを解くアルゴリズムの構築と理論解析である．2022年度では，研究課題に関連して，以下の成果を得た．共通するのは，線形計画問題の最適解を利用しているという点である．まず，密グラフを検出する問題において確率的な解（部分グラフに対する確率分布）を求める問題を扱った．時系列データなどの複数レイヤーをもつネットワークにおいて，どのレイヤーでも共通して密である部分を検出する問題は計算量的に難しいことが知られている．それでも何らかの解を求める必要があるときに用いる手段のひとつは，確率的な解を利用することである．本研究では，線形計画問題を用いて確率的な解を求めるアルゴリズムを提案した．この確率的な解は，効率的に計算できる「ネットワークの密っぽさ」の指標として用いることができる．この結果は国際会議WSDM2023で発表済みである．また，2018年度に行ったロバスト組合せ最適化問題に対する近似アルゴリズムの改良を行った．改良には，2019年度に行った公平割当問題のアルゴリズム設計手法を用いる．具体的には，線形計画問題に対する楕円体法と組合せ最適化問題の近似アルゴリズムを組み合わせることで，以前の研究で与えたアルゴリズムよりも良い理論保証をもつアルゴリズムを得られた．これらの結果は英文論文誌に投稿中である．他にも，エージェントに割り当て可能な財の集合に制約がある場合などの公平割当に関する研究を行い，国際会議で発表予定である．

这项研究的目的是构建具有组合约束的线性系统的算法和理论分析。在2022财年，获得了以下结果，该结果与研究主题有关：通常，它利用了线性编程问题的最佳解决方案。首先，我们解决了在检测密集图的问题中找到概率解决方案（子图的概率分布）的问题。众所周知，在具有多个图层（例如时间序列数据）的网络中，检测任何一层通常密集的区域的问题在计算上都是困难的。但是，当您仍然需要找到解决方案时，一种使用方法是使用概率解决方案。在这项研究中，我们提出了一种使用线性编程问题找到概率解决方案的算法。该概率解决方案可以用作可以有效计算的“网络密度”的指标。这些结果已经在国际会议WSDM2023上发布。此外，我们还改进了2018年实现的可靠组合优化问题的近似算法。为了进行改进，我们使用算法设计方法来解决2019年在2019年进行的公平分配问题。具体而言，通过将椭圆形方法与近似算法相结合的椭圆形方法与组合算法相结合，我们已经获得了近似算法，我们已经获得了组合算法。先前研究中给出的算法。这些结果目前已提交给英语期刊。此外，如果对可以分配给代理商的一组商品的限制并将在国际会议上进行限制，我们将对公平分配进行研究。

项目成果

National University of Singapore(シンガポール)

新加坡国立大学

Submodular Maximization with Uncertain Knapsack Capacity

背包容量不确定的子模最大化

• DOI: 10.1007/978-3-319-77404-6_48
• 发表时间: 2018
• 期刊: 13th Latin American Theoretical Informatics Symposium (LATIN 2018), Lecture Notes in Computer Science
• 作者: Kawase Yasushi;Sumita Hanna;Fukunaga Takuro
• 通讯作者: Fukunaga Takuro

Fair and Truthful Mechanism with Limited Subsidy.

公平真实的机制和有限的补贴。

• 发表时间: 2022
• 期刊: Proceedings of the 21st International Conference on Autonomous Agents and Multi-Agent Systems 2022 (AAMAS 2022)
• 作者: Hiromichi Goko;Ayumi Igarashi;Yasushi Kawase;Kazuhisa Makino;Hanna Sumita;Akihisa Tamura;Yu Yokoi;Makoto Yokoo
• 通讯作者: Makoto Yokoo

On the Max-min Fair Stochastic Allocation of Indivisible Goods

不可分割物品的最大最小公平随机分配

• 发表时间: 2020
• 期刊: Proceedings of the 34th AAAI Conference on Artificial Intelligence (AAAI2020)
• 作者: Kawase Yasushi;Yamaguchi Yutaro;Yokoi Yu;Yasushi Kawase and Atsushi Iwasaki;Yasushi Kawase and Hanna Sumita
• 通讯作者: Yasushi Kawase and Hanna Sumita

Optimal Matroid Partitioning Problems

• DOI: 10.1007/s00453-021-00797-9
• 发表时间: 2017-10
• 期刊: Algorithmica
• 影响因子: 1.1
• 作者: Yasushi Kawase;Kei Kimura;K. Makino;Hanna Sumita