WEKO3
アイテム
Toric ideal のstandard pair 分解と最小費用流問題
https://ipsj.ixsq.nii.ac.jp/records/31999
https://ipsj.ixsq.nii.ac.jp/records/31999b9f225ac-69f4-4fd6-8451-264d03133578
| 名前 / ファイル | ライセンス | アクション |
|---|---|---|
IPSJ-AL01082003.pdf (1.4 MB)
|
Copyright (c) 2002 by the Information Processing Society of Japan
|
|
| オープンアクセス | ||
| Item type | SIG Technical Reports(1) | |||||||
|---|---|---|---|---|---|---|---|---|
| 公開日 | 2002-01-24 | |||||||
| タイトル | ||||||||
| タイトル | Toric ideal のstandard pair 分解と最小費用流問題 | |||||||
| タイトル | ||||||||
| 言語 | en | |||||||
| タイトル | Standard pair decompositions of toric ideals and minimum cost flow problems | |||||||
| 言語 | ||||||||
| 言語 | jpn | |||||||
| 資源タイプ | ||||||||
| 資源タイプ識別子 | http://purl.org/coar/resource_type/c_18gh | |||||||
| 資源タイプ | technical report | |||||||
| 著者所属 | ||||||||
| 東京大学大学院理学系研究科情報科学専攻 | ||||||||
| 著者所属 | ||||||||
| 東京大学大学院情報理工学研究科コンピュータ科学専攻 | ||||||||
| 著者所属(英) | ||||||||
| en | ||||||||
| Department of Information Science , Graduate School of Science,The University of Tokyo | ||||||||
| 著者所属(英) | ||||||||
| en | ||||||||
| Department of Computer Science, Graduate School of Information Science and Technology,The University of Tokyo | ||||||||
| 著者名 |
石関, 隆幸
× 石関, 隆幸
|
|||||||
| 著者名(英) |
Takayuki, Ishizaki
× Takayuki, Ishizaki
|
|||||||
| 論文抄録 | ||||||||
| 内容記述タイプ | Other | |||||||
| 内容記述 | 近年、整数計画問題に対してトーリックイデアルの離散性により、グレブナ基底やstandard pair を用いた計算代数的アプローチが研究されている．これらのアプローチは既存の整数計画問題の解法に比べて計算量の改善を与えるものではないが、整数計画問題の構造について代数的な解析を与えている．本論文では、構造の知られている最小費用流問題に着目し，standard pair を用いた解析を行う．特に、トーリックイデアルのグレブナ基底および超幾何関数の結果を用いて、有向閉路を持たない有向グラフにおける最小費用流問題の（退化していない)双対多面体の頂点数の最小値が１になること，および最大値がカタラン数になることを示す． | |||||||
| 論文抄録(英) | ||||||||
| 内容記述タイプ | Other | |||||||
| 内容記述 | To integer programming problems,computational algebraic approaches using Grobner bases or standard paris via the discreteness of toric ideals have been studied in recent years. Although these approaches do not give improved time complexity bound compared with existing methods for solving integer programming problems,these give algebraic analysis of structure of integer programming problems.In this paper, we focus on the minimum cost flow problems,whose structure is well-known,and analyze using standard paris.Especially,using results about Grobner bases for toric ideals and hypergeometric functions, we show that the number of vertices of the (nondegenerate)dual polyhedra for minimum cost flow problems on acyclic directed graphs is more than 1 and less than the Catalan number. | |||||||
| 書誌レコードID | ||||||||
| 収録物識別子タイプ | NCID | |||||||
| 収録物識別子 | AN1009593X | |||||||
| 書誌情報 |
情報処理学会研究報告アルゴリズム（AL） 巻 2002, 号 7(2001-AL-082), p. 17-24, 発行日 2002-01-24 |
|||||||
| Notice | ||||||||
| SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc. | ||||||||
| 出版者 | ||||||||
| 言語 | ja | |||||||
| 出版者 | 情報処理学会 | |||||||
