Shapley-Folkman-type Theorem for Integrally Convex Sets

2023/05/24 by Kazuo Murota, Murota, Kazuo, Akihisa Tamura +1
Computer Science · Engineering · Mathematics · #52A41 #90C25 #90C27 #Automated Road and Building Extraction #Combinatorics (math.CO) #FOS: Mathematics #Point processes and geometric inequalities #Topological and Geometric Data Analysis

paper · pdf · doi:10.48550/arxiv.2305.15125

openalex publication_date 2023/05/24 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

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, L-natural-convex sets, and M-natural-convex sets, which are major classes of discrete convex sets in discrete convex analysis.

Related

• An Approximate Shapley-Folkman Theorem
• Decomposition of an Integrally Convex Set into a Minkowski Sum of Bounded and Conic Integrally Convex Sets
• Note on Minkowski Summation and Unimodularity in Discrete Convex Analysis
• Functional analogs of the Shephard, Busemann-Petty, and Milman problems
• Inclusion and Intersection Relations Between Fundamental Classes of Discrete Convex Functions