Exploration into Matroid Common Base Packing Problem

Matroid公共基础装箱问题探讨

基本信息

批准号：
20K19743
负责人：
山口勇太郎
金额：
$ 2.58万
依托单位：
Osaka University (2021-2022)Kyushu University (2020)
依托单位国家：
日本
项目类别：
Grant-in-Aid for Early-Career Scientists
财政年份：
2020
资助国家：
日本
起止时间：
2020-04-01 至 2024-03-31
项目状态：
已结题

来源：
https://kaken.nii.ac.jp/en/grant/KAKENHI-PROJECT-20K19743/
关键词：
マトロイド組合せ最適化アルゴリズム離散数学

项目摘要

マトロイド交叉分割に対する外側からのアプローチを考えている．マトロイド交叉分割は 3 マトロイド交叉の特殊ケースと見なせるが，3 マトロイド交叉問題は 3 次元マッチング問題やハミルトン閉路問題などの NP 困難な問題を含み，相当簡単なマトロイドに制限したとしても扱いやすい問題ではない．一方で，3 つのマトロイドを独立に選ばず，互いに関連させたような特殊ケースを考えると，扱いやすい場合がある．このような状況から，3 マトロイド交叉として捉えた場合に，「扱いやすさはどのような条件から導かれるのか」「どのような条件が扱いやすさに必要なのか」という観点からマトロイド交叉分割を再考している．マトロイド単体ではなくマトロイド交叉の離散構造としての扱いやすさの本質を追究する観点から，情報を制限したマトロイド交叉問題に対する研究も引き続き行っている．未だに完全解決には至っていないが，様々な情報の制限の仕方に対してある程度まとまった成果が得られたため，それらをまとめて未解決部分を問う論文を執筆した．当該論文は年度内に論文誌採録が決定し，その後の研究でさらに部分的な進展も得ている．マトロイド交叉の特殊ケースである 2 部マッチングに関する問題である割当問題に対して，古くから知られたハンガリー法の新たな変種とも見なせるアルゴリズムを設計し，ゲーム理論における公平分割問題に対する応用例とともに提案した．

我正在考虑一种外部方法来进行拟阵交叉划分。拟阵交叉划分可以看作是3-拟阵交叉的一个特例，但3-拟阵交叉问题包括3维匹配问题、哈密尔顿循环问题等NP难问题，即使它仅限于相当简单的拟阵。．另一方面，处理三个拟阵不是独立选择而是彼此相关的特殊情况可能更容易。基于这种情况，当被视为3-拟阵交叉时，我们将从“什么条件导致易于处理”和“什么条件是易于处理所必需的？”的角度来研究拟阵交叉划分。我正在重新考虑。从研究将拟阵交叉处理为离散结构而不是单个拟阵的难易性的角度来看，我们继续利用有限的信息对拟阵交叉问题进行研究。虽然我们还没有得出一个完整的解决方案，但关于各种限制信息的方法，我们已经取得了一些扎实的成果，因此我们写了一篇论文，对它们进行了总结，并对未解决的部分提出了质疑。该论文于年内被期刊接受收录，后续研究取得了进一步进展。对于分配问题，这是一个与二分匹配相关的问题，是拟阵交叉的一个特例，我们设计了一种算法，可以被认为是长期已知的匈牙利方法的新变体，并提出了它以及一个例子：其在博弈论公平分配问题中的应用．