Parametric bisubmodular function minimization and its associated signed ring family
-
- Fujishige, Satoru
- Research Institute for Mathematical Sciences, Kyoto University
Abstract
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.
Journal
-
- Discrete Applied Mathematics
-
Discrete Applied Mathematics 227 142-148, 2017-08-20
Elsevier B.V.
- Tweet
Details 詳細情報について
-
- CRID
- 1050282810828504448
-
- NII Article ID
- 120006346263
-
- ISSN
- 0166218X
-
- HANDLE
- 2433/227161
-
- Text Lang
- en
-
- Article Type
- journal article
-
- Data Source
-
- IRDB
- Crossref
- CiNii Articles
- KAKEN