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

数理計画問題に内在する大域的性質に基づく多項式時間アルゴリズムの構築

基于数学规划问题固有的全局属性构建多项式时间算法

基本信息

批准号：
18K11173
负责人：
森山園子
金额：
$ 2.75万
依托单位：
Nihon University
依托单位国家：
日本
项目类别：
Grant-in-Aid for Scientific Research (C)
财政年份：
2018
资助国家：
日本
起止时间：
2018-04-01 至 2024-03-31
项目状态：
已结题

来源：
https://kaken.nii.ac.jp/en/grant/KAKENHI-PROJECT-18K11173/
关键词：
数理計画多面体マトロイド数理計画問題

项目摘要

数理計画問題の解法として単体法[Dantzig(1947)]を起源とするピボットアルゴリズムがある。多項式時間を達成するピボットアルゴリズムの存在解明は数理計画問題における重要な未解決事項である。線形計画問題の一部を多項式回数の反復で解くアルゴリズムの達成[Gaertner(2002)]を機に，研究代表者はこの成功の核となった数理計画問題に内在する大域的性質に着目し，従来のピボットアルゴリズムが注視する数理計画問題の局所構造からは得られない大域的性質の重要性を明らかにしてきた。本研究では「(A)数理計画問題の大域的性質に基づく多項式時間ピボットアルゴリズムの構築」を目指して進めてきたが，そのアプローチの1つと想定していた「(B)離散勾配流によるピボットアルゴリズムの高速化の実現」について当初の想定より難しいことが判明した。また，22年度は私事により研究代表者の研究時間の確保が難しかったことから，最終年度の23年度（延長）に向けて研究計画の見直しをする必要が生じた。そこで，(A)を達成するうえで数理計画問題の多面体的構造の把握が重要であることと，もう1つの目標として「(C)マトロイドとその表現可能性からみた多面体の離散構造」があることから，23年度に向けて多面体の離散構造の把握に集中することにした。22年度は，20年度後半より開始した多面体とその計算に関する本の執筆を終え，現在校正段階である。本著を執筆する過程で多面体に関する書籍が少ないことを改めて認識し，本著より更に平易な内容を含む多面体の離散構造に関する別の書籍の執筆を開始した。

The origin of the solution to mathematical planning problems is the unit method [Dantzig(1947)]. Polynomial time is the key to solving mathematical problems. Gaertner(2002), a representative of the successful kernel and mathematical planning problem, studies the intrinsic properties of large domains in the linear planning problem. This study aims at "(A) the properties of large domains of mathematical programming problems, the construction of multi-domain polynomial systems," and "(B) the realization of high speed systems for discrete distributed flows." In 2012, the research representative's research time was guaranteed, and in 2013, the research plan was extended. (C) The possibility of representation of polyhedral discrete structures in mathematical planning problems. In the second half of 2012, the calculation of polyhedron was started, and the writing of polyhedron was finished. In the process of writing, the book has a lot of changes, and in the process of writing, the book has a lot of changes, and the book has a lot of changes.

项目成果

期刊论文数量（4）

专著数量（0）

科研奖励数量（0）

会议论文数量（0）

专利数量（0）

Smallest Counter examples for Convexity and Long-concavity of the Tutte Polynomial

Tutte多项式凸性和长凹性的最小反例

DOI：
发表时间：
2019
期刊：
影响因子：
0
作者：
[2]Hidefumi Hiraishi ;Hiroshi Imai;Sonoko Moriyama;Shuma Okamura and Shinya Shiroshita
通讯作者：
Shuma Okamura and Shinya Shiroshita

組合せ構造の幾何的実現可能性

组合结构的几何可行性