組合せ最適化問題の列挙アルゴリズムの構築

组合优化问题的枚举算法的构建

• 批准号: 10780279
• 负责人: 松井 泰子
• 金额: $ 1.22万
• 依托单位: Tokai University
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Encouragement of Young Scientists (A)
• 财政年份: 1998
• 资助国家: 日本
• 起止时间: 1998 至 1999
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/en/grant/KAKENHI-PROJECT-10780279/
• 关键词: 組合せ最適化; 列挙アルゴリズム; 重み付き多数決ゲーム

報告者は、今年度の科学研究費の支援により、以下の研究実績をあげることができた。1.重み付き多数決ゲームの指数計算をSurvey論文にまとめ発表した。発表論文中には、既存の研究の他、著者らによるオリジナルのアルゴリズムも掲載した。この論文は、ゲーム論,統計,確率、組合せ最適化と、多数の分野を含む充実した構成である。2.ヒッチコック問題の双対問題多面体の端点を、多項式遅延で列挙するアルゴリズムを構築し、現在、論文にまとめている。ヒッチコック問題の双対問題多面体の端点は、既存のアルゴリズムを利用して、列挙することは可能であるが、多項式遅延での列挙は実現されておらず、理論的計算量の側面からみると、興味深い結果であると思う。3.2値マトロイドのサーキット列挙問題を継続して研究中である。また、並行して、組合せ最適化問題に対するグレブナー基底の列挙問題の研究を行っている。今年度の業績をまとめると以下のとおりである。・査読付き論文1本(他、投稿中2本)、口頭発表2件。

在今年的科学研究资金的支持下，记者能够取得以下研究结果：1。我们在调查文件中编辑并发布了加权多数投票游戏的索引计算。除了现有研究外，发表的论文还具有作者的原始算法。本文具有全面的结构，其中包括游戏理论，统计，概率，组合优化和许多领域。 2。我们构建了一种算法，该算法列出了Hitchcock问题的双重问题多面体的终点，并以多项式延迟为单位，目前已在论文中编译。可以使用现有算法列举希区柯克问题的双重问题的终点，但是尚未实现用多项式延迟的枚举，我认为这是从理论计算复杂性的角度来看的有趣结果。 3。持续研究2值矩形的电路枚举问题。此外，我们一直在对Grebner基础枚举问题进行平行研究，以解决组合优化问题。今年的结果如下： - 1份同行评审的论文（其他2个帖子）和2个口头演示。

项目成果

森村 英典: "経営科学OR用語大事典" 朝倉邦造 (株式会社 朝倉書店), 726 (1999)

森村英德：《管理科学或术语百科全书》朝仓邦三（朝仓书店），726（1999）

Tomomi Matsui: "A Surveg of Algolithms for Calculating Power Indices of Weighted Majority Games"Journal of Operations Reserch Society of Japan. 43.1. 71-86 (2000)

Tomomi Matsui：“计算加权多数博弈实力指数的算法研究”日本运筹学会杂志。

Yasuko Matsui: "Complexity results for calculating power indices of weighted mazority games" Proceedings of International Conference on Nonlinear Anaiysis and Convex Analysis. (発表予定).

Yasuko Matsui：“计算加权多数博弈幂指数的复杂性结果”非线性分析和凸分析国际会议论文集（待提交）。