权益分类	功能权益	普通用户	{{item.name}}会员
{{category.name}}	{{benefitItem.name}}

Study of universal Grobner bases of zero-dimensional lattice ideals

零维晶格理想通用格罗布纳基的研究

基本信息

批准号：
15340007
负责人：
HIBI Takayuki
金额：
$ 5.5万
依托单位：
Osaka University
依托单位国家：
日本
项目类别：
Grant-in-Aid for Scientific Research (B)
财政年份：
2003
资助国家：
日本
起止时间：
2003 至 2005
项目状态：
已结题

来源：
https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-15340007/
关键词：
Grobner Basis Universal Grobner Basis Lattice Ideal Integer Programming Corner Polytope Finite Graph Toric Ideal Initial Ideal 隣接行列符号理論組合せ最適化問題 Gomory relaxation corner polyhedron

项目摘要

The lattice ideal of dimension zero appears in the research of both pure mathematics and applied mathematics. The original purpose of the present research project was to establish the algebraic theory of universal Groebner bases of lattice ideal of dimension zero and to study of its theoretical effectivity to commutative algebra and algebraic geometry as well as its practical effectivity to integer programming, coding theory together with algebraic statistics. First, we investigated the universal Groebner basis of the lattice ideal of dimension zero arising from the toric ideal of a finite graph and succeeded in describing its structure in terms of the finite graph. Second, in the study of a problem on integer programming arising from a finite graph for which Gomory's relaxation can be applied, we developed the technique to decide the estimation of the computational complexity of finding an optimal solution by using combinatorics on finite graphs. Third, we achieved the study of finding an explicit expression of the corner polyhedron of a lattice ideal of dimension zero in terms of the Minkowski sum of a bounded convex polytope and a convex cone, and obtained some results on the combinatorics of the polyhedral structure of the corner polyhedron. Finally, we developed the algebraic study on the Markov basis of the contingency table in algebraic statistics and presented a statistic model arising from a complete multipartite graph. These research results will contribute to the development of the algebraic study of integer programming. In addition, we organized two international meetings related with computational commutative algebra and Groebner bases.

零维格理想在纯数学和应用数学的研究中都有出现。本课题的研究目的是建立零维格理想的通用格罗布纳基的代数理论，研究其对交换代数和代数几何的理论有效性，以及对整数规划、编码理论和代数统计的实际有效性。首先，我们研究了由有限图的环理想产生的零维格理想的普遍格罗布纳基，并成功地用有限图描述了它的结构。其次，在研究可应用Gomory松弛的有限图的整数规划问题时，我们开发了利用有限图上的组合学来确定寻找最优解的计算复杂度的估计的技术。第三，我们研究了用有界凸多面体与凸锥的Minkowski和来表示零维格理想的角多面体，并得到了角多面体多面体结构的组合学的一些结果。最后，我们对代数统计中列联表的马尔可夫基础进行了代数研究，提出了一个由完全多部图产生的统计模型。这些研究成果将有助于整数规划的代数研究的发展。此外，我们还组织了两次有关计算交换代数和格罗布纳基的国际会议。