ダウンロード数: 304
このアイテムのファイル:
ファイル | 記述 | サイズ | フォーマット | |
---|---|---|---|---|
s13160-012-0084-y.pdf | 87.23 kB | Adobe PDF | 見る/開く |
タイトル: | Lattice polyhedra and submodular flows |
著者: | Fujishige, Satoru Peis, Britta |
著者名の別形: | 藤重, 悟 |
キーワード: | Lattice polyhedra Edmonds–Giles polyhedra Distributive lattices |
発行日: | Oct-2012 |
出版者: | Springer Japan |
誌名: | Japan Journal of Industrial and Applied Mathematics |
巻: | 29 |
号: | 3 |
開始ページ: | 441 |
終了ページ: | 451 |
抄録: | Lattice polyhedra, as introduced by Gröflin and Hoffman, form a common framework for various discrete optimization problems. They are specified by a lattice structure on the underlying matrix satisfying certain sub- and supermodularity constraints. Lattice polyhedra provide one of the most general frameworks of total dual integral systems. So far no combinatorial algorithm has been found for the corresponding linear optimization problem. We show that the important class of lattice polyhedra in which the underlying lattice is of modular characteristic can be reduced to the Edmonds–Giles polyhedra. Thus, submodular flow algorithms can be applied to this class of lattice polyhedra. In contrast to a previous result of Schrijver, we do not explicitly require that the lattice is distributive. Moreover, our reduction is very simple in that it only uses an arbitrary maximal chain in the lattice. |
著作権等: | The final publication is available at www.springerlink.com この論文は出版社版でありません。引用の際には出版社版をご確認ご利用ください。 This is not the published version. Please cite only the published version. |
URI: | http://hdl.handle.net/2433/167739 |
DOI(出版社版): | 10.1007/s13160-012-0084-y |
出現コレクション: | 学術雑誌掲載論文等 |
このリポジトリに保管されているアイテムはすべて著作権により保護されています。