二変数整数計画問題の幾何学的解法

• Item type: SIG Technical Reports(1)
• 公開日: 1993-11-25
• タイトル: 二変数整数計画問題の幾何学的解法
• タイトル / 言語: en
• タイトル: A Geometric Solution for the Two - variable Integer Programming
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 東京工業大学理工学研究科情報工学専攻渡辺研究室
• 著者所属(英): en
• 著者所属(英): Department of Computer Science, Tokyo Institute of Technology
• 著者名: 吉原, 貴仁
• 著者名(英): Kiyohito, Yoshihara
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 本論文では，二変数整数計画問題を解くアルゴリズムの一つを提案する．今回のアルゴリズムではまずはじめに与えられた実行可能領域をいくつかの三角形領域に分割する．そして最適解が存在すると思われる三角形領域から順に図形を小さくして解を求める手法を用いずにこれを求める．それによってn個の制約条件式からなる問題をO（ log n+K log ）の手間で解くことができる．但し，Kは分割した三角形領域の中で実際に最適解を探索したものの個数であり，K = O（）である．そしてLは与えられた問題中で最も絶対値の大きい数である．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: In this paper, we propose a geometric algorithm for the solving two-variable integer programming problem. This algorithm divides a given feasible region into triangles and searches the optimal solution within the triangular regions in the order we expect the optimal solution to exist. This algorithm can solve the problem with n constraints in O (n log n + K log L) time, where K is the number of the triangles actually searched in the algorithm, L is the maximum absolute value of numbers in the given problem.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN1009593X
• 書誌情報: 情報処理学会研究報告アルゴリズム（AL）; 巻 1993, 号 104(1993-AL-036), p. 49-56, 発行日 1993-11-25
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会