NewDevelopments of Discrete-System Algorithmics Based on Complexes

基于复形的离散系统算法的新进展

• 批准号: 10205204
• 负责人: IMAI Hiroshi
• 金额: $ 6.98万
• 依托单位: The University of Tokyo
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Scientific Research on Priority Areas (B)
• 财政年份: 1998
• 资助国家: 日本
• 起止时间: 1998 至 2000
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-10205204/
• 关键词: simplicial complex; discrete system; invariant polynomials; Tutte polynomial; Binary Decision Diagram (BDD); Groebner bases; quantun information; マトロイド; Grobner基底; 計算幾何・計算代数; 最適化; 情報幾何; Voronoi図

Simplicial complexes arise in various discrete systems, such as graphs, networks, matroids, convex polytopes, triangulations, etc. There have been known discrete invariant polynomials featuring a given simplicial complex, such as network reliability, chromatic polynomial, invariants of statistical physics and knots/links. We have developed efficient algorithms to compute these invariant polynomials based on the Binary Decision Diagram (BDD), and have shown that moderate-size problems can be solved in practice. Since most of these computation problems are known to be #P-hard, this is a quite remarkable result. We have also presented algebraic approaches to these problems, based on the Groebner bases in computational algebra and also triangulations in computational geometry. This unified approach was analyzed from the viewpoint of combinatorial complexity. We have further investigated new search methods for combinatorial search, geometric and probabilistic proximity structures, full text database search algorithms, etc. Finally, quantum computing and quantum information theory are treated as a natural extension of probabilistic computation and classical information theory, and their discrete structures have been revealed. In so doing, quantum computation simulators have been implemented and used. Some submodularity property of the quantum entropy is also shown.

单纯复形出现在各种离散系统中，如图、网络、拟阵、凸多面体、三角剖分等。已知的离散不变多项式具有给定的单纯复形，如网络可靠性、色多项式、统计物理和节点/链接的不变量。我们已经开发出有效的算法来计算这些不变的多项式的基础上的二元决策图（BDD），并已表明，中等规模的问题可以在实践中解决。由于这些计算问题中的大多数已知是#P-hard的，因此这是一个非常显着的结果。我们还基于计算代数中的Groebner基和计算几何中的三角测量，提出了解决这些问题的代数方法。从组合复杂性的角度分析了这种统一方法。我们进一步研究了新的搜索方法组合搜索，几何和概率邻近结构，全文数据库搜索算法等，最后，量子计算和量子信息理论被视为一个自然的扩展概率计算和经典信息理论，其离散结构已被揭示。在这样做的过程中，量子计算模拟器已经被实现和使用。同时也证明了量子熵的子模性质。

项目成果

石関隆幸、今井浩: "トーナメントグラフのトーリックイデアルのGrobner基底について"情報処理学会SIGAL. (1999)

Takayuki Ishizeki、Hiroshi Imai：“关于锦标赛图的环面理想的 Grobner 基础”，日本信息处理协会 SIGAL (1999)。

T.Ikeda and H.Imai: "Enhauced A^* Algorithms for Multiple Alignments : Optimal Alignments for Several Sequences and \K\-Opt Aporaximate Alignments for Large Cases" Theoretical Computer Science. vol.210, No.2. 341-374 (1999)

T.Ikeda 和 H.Imai：“用于多重比对的增强 A^* 算法：多个序列的最佳比对和大型案例的 K-Opt 近似比对”理论计算机科学。

浅野孝夫,今井浩: "計算とアルゴリズム"オーム社. 295 (2000)

Takao Asano，Hiroshi Imai：“计算和算法”Ohmsha 295 (2000)。

T.Ishizeki and H.Imai: "Grobner Bases of Acyclic Tournament Graphs and Hypergeometric Systems on the Group of Unipotent Matrices"京都大学数理解析研究所講究録. 1171. 7-20 (2000)

T.Ishizeki 和 H.Imai：“单能矩阵群上的非循环锦标赛图和超几何系统的 Grobner 基”京都大学数学科学研究所 Kokyuroku。1171. 7-20 (2000)。

T.Ishizeki and H.Imai: "Grobner Bases for Toric Ideals of Acyclic Directed Graphs and Their Applications to Minimum Cost Flow Problem"統計数理研究所共同研究レポート. 135. 152-165 (2000)

T.Ishizeki 和 H.Imai：“无环有向图环面理想的 Grobner 基础及其在最小成本流问题中的应用”统计数学研究所联合研究报告 135. 152-165 (2000)。