ダウンロード数: 144
このアイテムのファイル:
ファイル | 記述 | サイズ | フォーマット | |
---|---|---|---|---|
j.dam.2017.04.047.pdf | 61.22 kB | Adobe PDF | 見る/開く |
タイトル: | Parametric bisubmodular function minimization and its associated signed ring family |
著者: | Fujishige, Satoru |
著者名の別形: | 藤重, 悟 |
キーワード: | Bisubmodular function Signed ring family Signed poset Principal partition |
発行日: | 20-Aug-2017 |
出版者: | Elsevier B.V. |
誌名: | Discrete Applied Mathematics |
巻: | 227 |
開始ページ: | 142 |
終了ページ: | 148 |
抄録: | The present paper shows an extension of the theory of principal partitions for submodular functions to that for bisubmodular functions. We examine the structure of the collection of all solutions of a parametric minimization problem described by a bisubmodular function and two vectors. The bisubmodular function to be minimized for each parameter is the sum of the bisubmodular function and a parameterized box-bisubmodular function given in terms of the two vectors. We show that the collection of all the minimizers for all parameters forms a signed ring family and it thus induces a signed poset on a signed partition of the underlying set. We further examine the structure of the signed ring family and reveal the decomposition structure depending on critical values of the parameter. Moreover, we discuss the relation between the results of this paper on bisubmodular functions and the theory of principal partitions developed for submodular functions. |
著作権等: | © 2017. This manuscript version is made available under the CC-BY-NC-ND 4.0 license http://creativecommons.org/licenses/by-nc-nd/4.0/ The full-text file will be made open to the public on 20 August 2019 in accordance with publisher's 'Terms and Conditions for Self-Archiving' This is not the published version. Please cite only the published version. この論文は出版社版でありません。引用の際には出版社版をご確認ご利用ください。 |
URI: | http://hdl.handle.net/2433/227161 |
DOI(出版社版): | 10.1016/j.dam.2017.04.047 |
出現コレクション: | 学術雑誌掲載論文等 |
このリポジトリに保管されているアイテムはすべて著作権により保護されています。