離散凸解析における双対理論の深化

深化离散凸分析中的对偶理论

• 批准号: 22K17854
• 负责人: 岩政 勇仁
• 金额: $ 2.91万
• 依托单位: Kyoto University
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Early-Career Scientists
• 财政年份: 2022
• 资助国家: 日本
• 起止时间: 2022-04-01 至 2027-03-31
• 项目状态: 未结题
• 来源: https://kaken.nii.ac.jp/en/grant/KAKENHI-PROJECT-22K17854/
• 关键词: 双劣モジュラ関数; 共役性; 交換公理; 単体的複体; 組合せ最適化; 双対性; 離散凸解析

離散凸解析における重要な関数クラスであるL凸関数は，ある特別な単体的複体の頂点上に定義された関数とみなすことができる．そこで「どのような単体的複体上なら適切にL凸性を拡張できるか」を念頭に，単体的複体の理論や性質に関する調査を行った．その過程で，球面と同相な単体的複体の頂点彩色間の遷移に対して，その遷移可能性をある程度特徴づける良い不変量や，遷移可能性判定問題の計算量の解析を行った．本研究成果は，"Reconfiguration of colorings in triangulations of the sphere"として論文にまとめ，理論計算幾何学のトップカンファレンスであるInternational Symposium on Computational Geometry (SoCG)に採択された．また，これに関連して，遷移制約を入れた彩色遷移に関する研究"Algorithms for coloring reconfiguration under recolorability digraphs"が理論計算機科学の国際会議であるInternational Symposium on Algorithms and Computation (ISAAC)に採択された．本研究課題に関する基礎研究として，双劣モジュラ関数の共役に対応するBS凸集合に対する「hole-free性を仮定しない交換公理的な特徴づけ」を与えた．この成果は"Characterizations of the set of integer points in an integral bisubmodular polyhedron"として論文にまとめ，現在査読付き国際論文誌に投稿中である．

Discrete convex analysis is important for the definition of the complex vertex of a particular entity. The idea of "the convexity of a single complex" is to investigate the theoretical properties of a single complex. In the process, the transition between vertex colors of complex of spherical and in-phase single bodies is related to the degree of migration possibility. The results of this study are presented in the paper entitled "Reconfiguration of colours in triangulation of the sphere." International Symposium on Computational Geometry (SoCG). The International Symposium on Algorithms and Computation (ISAAC) was held at the International Conference on Theoretical Computer Science. This research topic is related to the basic research of "hole-free property" and "commutative axiom". This paper is entitled "Characteristics of the set of integer points in an integral bimodular polyhedron."

项目成果

研究成果

研究结果

Reconfiguration of colorings in triangulations of the sphere

球体三角剖分中颜色的重新配置

• 发表时间: 2023
• 期刊: Proceedings of the 39th International Symposium on Computational Geometry (SoCG 2023)
• 作者: Takehiro Ito;Yuni Iwamasa;Yusuke Kobayashi;Shun-ichi Maezawa;Yuta Nozaki;Yoshio Okamoto;and Kenta Ozeki
• 通讯作者: and Kenta Ozeki

整数双劣モジュラ多面体の整数点集合の特徴づけ

整数双子模多面体的整数点集的表征

• 发表时间: 2023
• 作者: Soichiro Fujii;Yuni Iwamasa;Kei Kimura;and Akira Suzuki;岩政 勇仁
• 通讯作者: 岩政 勇仁

球面の三角形分割の彩色遷移

球面三角剖分的着色过渡

• 发表时间: 2022
• 作者: Soichiro Fujii;Yuni Iwamasa;Kei Kimura;and Akira Suzuki;岩政 勇仁;Yuni Iwamasa;岩政 勇仁
• 通讯作者: 岩政 勇仁

Algorithms for Coloring Reconfiguration Under Recolorability Digraphs

• DOI: 10.4230/lipics.isaac.2022.4
• 发表时间: 2022
• 作者: Soichiro Fujii;Yuni Iwamasa;Keiichi Kimura;Akira Suzuki