双二次最終多項式による有向マトロイドの実現不可能性判定

• Item type: SIG Technical Reports(1)
• 公開日: 2005-01-20
• タイトル: 双二次最終多項式による有向マトロイドの実現不可能性判定
• タイトル / 言語: en
• タイトル: Deciding non-realizability of oriented matroids by biquadratic final polynomials
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 東京大学大学院情報理工学系研究科
• 著者所属: Department of Mathematics Swiss Federal Institute of Technology Zurich
• 著者所属: Department of Mathematics Swiss Federal Institute of Technology Lausanne
• 著者所属: Department of Computer Science Swiss Federal Institute of Technology Zurich
• 著者所属(英): en
• 著者所属(英): Graduate School of Information Science and Technology, The University of Tokyo
• 著者所属(英): en
• 著者所属(英): Department of Mathematics, Swiss Federal Institute of Technology Zurich
• 著者所属(英): en
• 著者所属(英): Department of Mathematics, Swiss Federal Institute of Technology Lausanne
• 著者所属(英): en
• 著者所属(英): Department of Computer Science, Swiss Federal Institute of Technology Zurich
• 著者名: 中山, 裕貴; 森山, 園子; 福田, 公明; 岡本, 吉央
• 著者名(英): Hiroki, Nakayama; Sonoko, Moriyama; Komei, Fukuda; Yoshio, Okamoto
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 有向マトロイドとは，実ベクトル空間Rnのベクトル配置を抽象化した組合せモデルである．有向マトロイドはRnのベクトル配置から得られるとき実現可能であるというが，この判定問題はNP困難であることが知られている．実現不可能な有向マトロイドを判定する手段としては，Holt-Klee条件を基にしたnon-HK*性や，双二次最終多項式を用いた手法が提案されている． 我々は台集合の要素数が8 ランクが4の有向マトロイドに着目する．このような有向マトロイドで一様なものは同型を除いて2628個あり，うち24個が実現不可能であることが知られているが，その証明は双二次最終多項式により，浮動小数点演算を用いて行われていた．本研究では，同手法を有理数演算を用いて適用し，実現不可能な24個の有向マトロイド全てを列挙した．さらに，非一様な有向マトロイドで，双二次最終多項式では発見できない実現不可能な有向マトロイドが存在することも示した．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: An oriented matroid is a combinatorial model obtained as an abstraction of a vector configuration in a real vector space R^n. An oriented matroid is defined realizable if it is obtained from a vector configuration in R^n, but deciding realizability of an oriented matroid is known to be NP-hard. Hence the methods using non-HK*, which are based on Holt-Klee condition, and using biquadratic final polynomial, are proposed. Now we focus on rank-4 oriented matroids on a 8-element ground set. It is known that there exist 2628 such uniform oriented matroids, and 24 of them are non-realizable. Their specific form were obtained by biquadratic final polynomials with floating-point arithmetic. In our study, we find all such 24 matroids by a same method with exact rational arithmetic. Furthermore, we show there exist non-realizable non-uniform oriented matroids which have no biquadratic final polynomial.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN1009593X
• 書誌情報: 情報処理学会研究報告アルゴリズム（AL）; 巻 2005, 号 5(2004-AL-099), p. 23-29, 発行日 2005-01-20
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会