ダウンロード数: 525
このアイテムのファイル:
ファイル | 記述 | サイズ | フォーマット | |
---|---|---|---|---|
978-3-540-76796-1_7.pdf | 218.43 kB | Adobe PDF | 見る/開く |
タイトル: | Theory of Principal Partitions Revisited |
著者: | Fujishige, Satoru |
著者名の別形: | 藤重, 悟 |
発行日: | 2009 |
出版者: | Springer |
引用: | A chapter from Cook, William, László Lovász, and Jens Vygen, eds. 2009. Research Trends in Combinatorial Optimization. Berlin, Heidelberg: Springer Berlin Heidelberg. |
開始ページ: | 127 |
終了ページ: | 162 |
抄録: | The theory of principal partitions of discrete systems such as graphs, matrices, matroids, and submodular systems has been developed since 1968. In the early stage of the developments during 1968–75 the principal partition was considered as a decomposition of a discrete system into its components together with a partially ordered structure of the set of the components. It then turned out that such a decomposition with a partial order on it arises from the submodularity structure pertinent to the system and it has been realized that the principal partitions are closely related to resource allocation problems with submodular structures, which are kind of dual problems. The aim of this paper is to give an overview of the developments in the theory of principal partitions and some recent extensions with special emphasis on its relation to associated resource allocation problems in order to make it better known to researchers in combinatorial optimization. |
著作権等: | 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/137597 |
DOI(出版社版): | 10.1007/978-3-540-76796-1_7 |
出現コレクション: | 学術雑誌掲載論文等 |
このリポジトリに保管されているアイテムはすべて著作権により保護されています。