学術雑誌論文 Parametric bisubmodular function minimization and its associated signed ring family

Fujishige, Satoru

227pp.142 - 148 , 2017-08-20 , Elsevier B.V.
ISSN:0166-218X
内容記述
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.
本文を読む

http://repository.kulib.kyoto-u.ac.jp/dspace/bitstream/2433/227161/1/j.dam.2017.04.047.pdf

このアイテムのアクセス数:  回

その他の情報