Advances in Theory and Design Principles of Counting AlgorithmsBased on Polyhedral Combinatorics

基于多面体组合的计数算法理论与设计原理研究进展

• 批准号: 21700009
• 负责人: OKAMOTO Yoshio
• 金额: $ 2.66万
• 依托单位: The University of Electro-Communications (2011)Japan Advanced Institute of Science and Technology (2010)Tokyo Institute of Technology (2009)
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Young Scientists (B)
• 财政年份: 2009
• 资助国家: 日本
• 起止时间: 2009 至 2011
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-21700009/
• 关键词: アルゴリズム; 離散数学; 凸多面体; グラフ; 離散幾何

Results on counting problems for graphs, counting problems for discrete and computational geometry, and their applications to optimization problems were obtained. For example, the computational complexity of counting the dominating sets in a graph was investigated from the perspective of graph classes, and a polynomial-time algorithm to find a global optimal solution to the distance function maximization was developed by efficiently enumerating all local optimal solutions. These results were presented in refereed international journals and refereed international conferences.

给出了图的计数问题、离散几何和计算几何的计数问题及其在优化问题中的应用。例如，从图类的角度研究了图中支配集计数的计算复杂度，提出了一种通过有效枚举所有局部最优解来求距离函数最大化全局最优解的多项式时间算法。这些结果发表在国际期刊和国际会议上。

项目成果

Approximating the path-distance-width for AT-free graphs and graphs in related classes

近似无 AT 图和相关类中的图的路径距离宽度

• DOI: 10.1016/j.dam.2012.11.015
• 发表时间: 2013
• 期刊: Discrete Applied Mathematics
• 影响因子: 1.1
• 作者: Yota Otachi;Toshiki Saitoh;Katsuhisa Yamanaka;Shuji Kijima;Yoshio Okamoto;Hirotaka Ono;Yushi Uno;and Koichi Yamazaki
• 通讯作者: and Koichi Yamazaki

On Problems as Hard as CNFSAT

• DOI: 10.1145/2925416
• 发表时间: 2011-12
• 期刊: ArXiv
• 作者: Marek Cygan;Holger Dell;D. Lokshtanov;D. Marx;Jesper Nederlof;Y. Okamoto;R. Paturi;Saket Saurabh

A polynomial-time-delay polynomial-space algorithm for enumeration problems in multi-criteria optimization

多标准优化中枚举问题的多项式时滞多项式空间算法

• DOI: 10.1016/j.ejor.2010.10.008
• 发表时间: 2011
• 期刊: European Journal of Operational Research
• 影响因子: 6.4
• 作者: Yoshio Okamoto;Yota Otachi;Ryuhei Uehara;and Takeaki Uno;Kazushige Terui;Kazushige Terui;照井一成;Yoshio Okamoto and Takeaki Uno
• 通讯作者: Yoshio Okamoto and Takeaki Uno

間違えても大丈夫な凸包構成アルゴリズム

即使犯错误也安全的凸包构造算法

• 发表时间: 2011
• 期刊: 情報処理学会アルゴリズム研究会研究報告
• 作者: Heidi Gebauer;Anna Gundert;Robin A. Moser;and Yoshio Okamoto;K.Terui;K. Terui;ワルター ディディモ，ミヒャエル カウフマン，ジウセッペ リオッタ，岡本 吉央，アンドレアス シュピルナー;K.Terui;岡本 吉央，大舘 陽太，上原 隆平，宇野 毅明;K.Terui;岡本 吉央，ステファン ランガマン
• 通讯作者: 岡本 吉央，ステファン ランガマン

費用2種類の施設配置ゲームの仁とシャープレイ値の計算について

关于两种成本的设施放置游戏中Jin和Shapley值的计算

• 发表时间: 2013
• 期刊: 情報処理学会研究報告アルゴリズム
• 作者: Yota Otachi;Toshiki Saitoh;Katsuhisa Yamanaka;Shuji Kijima;Yoshio Okamoto;Hirotaka Ono;Yushi Uno;and Koichi Yamazaki;岡本 吉央;並河 雄紀，岡本 吉央，大舘 陽太
• 通讯作者: 並河 雄紀，岡本 吉央，大舘 陽太