TY - JOUR
T1 - Every finite distributive lattice is isomorphic to the minimizer set of an M♮-concave set function
AU - Fujii, Tomohito
AU - Kijima, Shuji
N1 - Funding Information:
The authors are grateful to Kazuo Murota for his suggestion about the problem, and for his kind advice on their preliminary manuscript. The authors are also grateful to Satoru Fujishige, Akihisa Tamura, Naoyuki Kamiyama and anonymous reviewers for their valuable comments. This work was partly supported by JST PRESTO Grant Number JPMJPR16E4 , Japan.
Funding Information:
The authors are grateful to Kazuo Murota for his suggestion about the problem, and for his kind advice on their preliminary manuscript. The authors are also grateful to Satoru Fujishige, Akihisa Tamura, Naoyuki Kamiyama and anonymous reviewers for their valuable comments. This work was partly supported by JST PRESTO Grant Number JPMJPR16E4, Japan.
Publisher Copyright:
© 2020 Elsevier B.V.
PY - 2021/1
Y1 - 2021/1
N2 - M♮-concavity is a key concept in discrete convex analysis. For set functions, the class of M♮-concavity is a proper subclass of submodularity. It is a well-known fact that the set of minimizers of a submodular function forms a distributive lattice, where every finite distributive lattice is possible to appear. It is a natural question whether every finite distributive lattice appears as the minimizer set of an M♮-concave set function. This paper affirmatively answers the question.
AB - M♮-concavity is a key concept in discrete convex analysis. For set functions, the class of M♮-concavity is a proper subclass of submodularity. It is a well-known fact that the set of minimizers of a submodular function forms a distributive lattice, where every finite distributive lattice is possible to appear. It is a natural question whether every finite distributive lattice appears as the minimizer set of an M♮-concave set function. This paper affirmatively answers the question.
UR - http://www.scopus.com/inward/record.url?scp=85096163095&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85096163095&partnerID=8YFLogxK
U2 - 10.1016/j.orl.2020.10.012
DO - 10.1016/j.orl.2020.10.012
M3 - Article
AN - SCOPUS:85096163095
SN - 0167-6377
VL - 49
SP - 1
EP - 4
JO - Operations Research Letters
JF - Operations Research Letters
IS - 1
ER -