単調線形システムにおけるすべての極小な整数解について

• Item type: SIG Technical Reports(1)
• 公開日: 2001-05-18
• タイトル: 単調線形システムにおけるすべての極小な整数解について
• タイトル / 言語: en
• タイトル: All Minimal Integer Solutions for a Monotone System of Linear Inequalities
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: RUTCOR Rutgers University
• 著者所属: Department of Computer Science Rutgers University
• 著者所属: RUTCOR Rutgers University
• 著者所属: Department of Computer Science Rutgers University
• 著者所属: 大阪大学大学院基礎工学研究科システム科学分野
• 著者所属(英): en
• 著者所属(英): RUTCOR,Rutgers University
• 著者所属(英): en
• 著者所属(英): Department of Computer Science,Rutgers University
• 著者所属(英): en
• 著者所属(英): RUTCOR,Rutgers University
• 著者所属(英): en
• 著者所属(英): Department of Computer Science,Rutgers University
• 著者所属(英): en
• 著者所属(英): Division of Systems Science, Graduate School of Engineering Science,Osaka University
• 著者名: Endre, Boros; Khaled, Elbassioni; Vladimir, Gurvich; Leonid, Khachiyan; 牧野, 和久
• 著者名(英): Endre, Boros; Khaled, Elbassioni; Vladimir, Gurvich; Leonid, Khachiyan; Kazuhisa, Makino
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 本論文では 単調線形システムのすべての極小な整数解を列挙する問題について考える．我々は，まず，r 個の線形不等式から成るどんなn 変数単調線形システムにおいても，極大な実行不可能整数解の数が極小な実行可能整数解の数の高々rn 倍であることを示す．このことにより，単調線形システムにおける極小整数解列挙問題が有名なハイパーグラフ双対化問題の自然な拡張に多項式時間還元可能であることが導かれる．ここで，ハイパーグラフ双対化問題の拡張とは，ハイパーグラフの双対ペアを整数ベクトルの双対族に置き換えるという意味での拡張である．我々はこの拡張された双対化問題に対する擬多項式時間アルゴリズムを構成する．これらの結果は，特に，単調線形システムにおけるすべての極小な整数解が逐次擬多項式時間で列挙可能であることを意味する．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: We consider the problem of enumerating all minimal integer solutions of a monotone system of linear inequalities.We first show that for any monotone system of r linear inequalities in n variables, the number of maximal infeasible integer vectors is at most rn times the umber of minimal integer solutions to the system.This bound leads to a polynomial-time reduction of the enumeration problem to a natural generalization of the well-known dualization problem for hypergraphs,in which dual pairs of hypergraphs are replaced by dual collections of integer vectors in a box.We provide a quasi-polynomial algorithm for the latter dualization problem.These results imply,in particular,that the problem of incrementally generating all minimal integer solutions to a monotone system of linear inequalities can be done in quasi-polynomial time.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN1009593X
• 書誌情報: 情報処理学会研究報告アルゴリズム（AL）; 巻 2001, 号 43(2001-AL-078), p. 19-26, 発行日 2001-05-18
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会