Shapley–Folkman-type theorem for integrally convex sets

Kazuo Murota; Akihisa Tamura

doi:10.1016/j.dam.2024.08.015

Shapley–Folkman-type theorem for integrally convex sets

Kazuo Murota, Akihisa Tamura

Department of Mathematics

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

Abstract

The Shapley–Folkman theorem is a statement about the Minkowski sum of (non-convex) sets, expressing the closeness of the Minkowski sum to convexity in a quantitative manner. This paper establishes similar theorems for integrally convex sets, M^♮-convex sets, and L^♮-convex sets, which are major classes of discrete convex sets in discrete convex analysis.

Original language	English
Pages (from-to)	42-50
Number of pages	9
Journal	Discrete Applied Mathematics
Volume	360
DOIs	https://doi.org/10.1016/j.dam.2024.08.015
Publication status	Published - 2025 Jan 15

Keywords

Discrete convex analysis
Integrally convex set
L-convex set
M-convex set
Minkowski sum
Shapley–Folkman theorem

ASJC Scopus subject areas

Discrete Mathematics and Combinatorics
Applied Mathematics

Access to Document

10.1016/j.dam.2024.08.015

Cite this

@article{75072b3e7b7f40f890c7125448da5095,

title = "Shapley–Folkman-type theorem for integrally convex sets",

abstract = "The Shapley–Folkman theorem is a statement about the Minkowski sum of (non-convex) sets, expressing the closeness of the Minkowski sum to convexity in a quantitative manner. This paper establishes similar theorems for integrally convex sets, M♮-convex sets, and L♮-convex sets, which are major classes of discrete convex sets in discrete convex analysis.",

keywords = "Discrete convex analysis, Integrally convex set, L-convex set, M-convex set, Minkowski sum, Shapley–Folkman theorem",

author = "Kazuo Murota and Akihisa Tamura",

note = "Publisher Copyright: {\textcopyright} 2024 The Author(s)",

year = "2025",

month = jan,

day = "15",

doi = "10.1016/j.dam.2024.08.015",

language = "English",

volume = "360",

pages = "42--50",

journal = "Discrete Applied Mathematics",

issn = "0166-218X",

publisher = "Elsevier B.V.",

}

TY - JOUR

T1 - Shapley–Folkman-type theorem for integrally convex sets

AU - Murota, Kazuo

AU - Tamura, Akihisa

PY - 2025/1/15

Y1 - 2025/1/15

N2 - The Shapley–Folkman theorem is a statement about the Minkowski sum of (non-convex) sets, expressing the closeness of the Minkowski sum to convexity in a quantitative manner. This paper establishes similar theorems for integrally convex sets, M♮-convex sets, and L♮-convex sets, which are major classes of discrete convex sets in discrete convex analysis.

AB - The Shapley–Folkman theorem is a statement about the Minkowski sum of (non-convex) sets, expressing the closeness of the Minkowski sum to convexity in a quantitative manner. This paper establishes similar theorems for integrally convex sets, M♮-convex sets, and L♮-convex sets, which are major classes of discrete convex sets in discrete convex analysis.

KW - Discrete convex analysis

KW - Integrally convex set

KW - L-convex set

KW - M-convex set

KW - Minkowski sum

KW - Shapley–Folkman theorem

UR - http://www.scopus.com/inward/record.url?scp=85202561141&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85202561141&partnerID=8YFLogxK

U2 - 10.1016/j.dam.2024.08.015

DO - 10.1016/j.dam.2024.08.015

M3 - Article

AN - SCOPUS:85202561141

SN - 0166-218X

VL - 360

SP - 42

EP - 50

JO - Discrete Applied Mathematics

JF - Discrete Applied Mathematics

ER -

Shapley–Folkman-type theorem for integrally convex sets

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this