Every finite distributive lattice is isomorphic to the minimizer set of an M♮-concave set function

Tomohito Fujii; Shuji Kijima

doi:10.1016/j.orl.2020.10.012

Every finite distributive lattice is isomorphic to the minimizer set of an M^♮-concave set function

Tomohito Fujii, Shuji Kijima

Mathematical Informatics

Research output: Contribution to journal › Article › peer-review

Abstract

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.

Original language	English
Pages (from-to)	1-4
Number of pages	4
Journal	Operations Research Letters
Volume	49
Issue number	1
DOIs	https://doi.org/10.1016/j.orl.2020.10.012
Publication status	Published - Jan 2021

All Science Journal Classification (ASJC) codes

Software
Management Science and Operations Research
Industrial and Manufacturing Engineering
Applied Mathematics

Access to Document

10.1016/j.orl.2020.10.012

Cite this

@article{1ecbaa9de4594e018918b1d1adced7ce,

title = "Every finite distributive lattice is isomorphic to the minimizer set of an M♮-concave set function",

abstract = "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.",

author = "Tomohito Fujii and Shuji Kijima",

note = "Publisher Copyright: {\textcopyright} 2020 Elsevier B.V.",

year = "2021",

month = jan,

doi = "10.1016/j.orl.2020.10.012",

language = "English",

volume = "49",

pages = "1--4",

journal = "Operations Research Letters",

issn = "0167-6377",

publisher = "Elsevier B.V.",

number = "1",

}

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

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 -

Every finite distributive lattice is isomorphic to the minimizer set of an M^♮-concave set function

Abstract

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this