Note on the polyhedral description of the Minkowski sum of two L-convex sets

DOI10.1007/S13160-022-00512-3MaRDI QIDQ2111552zbMATH OpenOpenAlexFDO

Authors Satoko Moriguchi, Kazuo Murota

Publication date 17 January 2023

Published in Japan Journal of Industrial and Applied Mathematics (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/2110.10445

zbMATH Keywords

Minkowski sumdiscrete convex analysisFourier-Motzkin eliminationL-convex set\(\mathrm{L}_2\)-convex set

Mathematics Subject Classification ID

Convex programming (90C25) Combinatorial optimization (90C27) Convex functions and convex programs in convex geometry (52A41)

Abstract: L-convex sets are one of the most fundamental concepts in discrete convex analysis. Furthermore, the Minkowski sum of two L-convex sets, called L2-convex sets, is an intriguing object that is closely related to polymatroid intersection. This paper reveals the polyhedral description of an L2-convex set, together with the observation that the convex hull of an L2-convex set is a box-TDI polyhedron. Two different proofs are given for the polyhedral description. The first is a structural short proof, relying on the conjugacy theorem in discrete convex analysis, and the second is a direct algebraic proof, based on Fourier-Motzkin elimination. The obtained results admit natural graph representations. Implications of the obtained results in discrete convex analysis are also discussed.

Recommendations

• On convolution ofL-convex functions
• On polyhedral approximation of L-convex and M-convex functions
• Discrete Convex Analysis
• Discrete convexity
• Notes on L-/M-convex functions and the separation theorems

Cites work

• scientific article; zbMATH DE number 3885657 (Why is no real title available?)
• scientific article; zbMATH DE number 4089320 (Why is no real title available?)
• A discrete convex min-max formula for box-TDI polyhedra
• A survey of fundamental operations on discrete convex functions of various kinds
• ALGORITHMS FOR L-CONVEX FUNCTION MINIMIZATION: CONNECTION BETWEEN DISCRETE CONVEX ANALYSIS AND OTHER RESEARCH FIELDS
• Box-total dual integrality, box-integrality, and equimodular matrices
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Convex Polytopes
• Dijkstra's algorithm and L-concave function maximization
• Directed discrete midpoint convexity
• Discrete Convex Analysis
• Discrete convex analysis
• Discrete midpoint convexity
• Extremal Splittings of Point Processes
• Generalized polymatroids and submodular flows
• Integrality of subgradients and biconjugates of integrally convex functions
• Lectures on Polytopes
• Note on Multimodularity and L-Convexity
• On box totally dual integral polyhedra
• On fundamental operations for multimodular functions
• On matroid intersection adjacency
• Operations that preserve total dual integrality
• Recent developments in discrete convex analysis
• Relationship of M-/L-convex functions with discrete convex functions by Miller and Favati-Tardella.
• Submodular functions and optimization.
• The logic of logistics. Theory, algorithms, and applications for logistics management

Cited in

(2)

• Decomposition of an Integrally Convex Set into a Minkowski Sum of Bounded and Conic Integrally Convex Sets
• Recent progress on integrally convex functions

This page was built for publication: Note on the polyhedral description of the Minkowski sum of two L-convex sets

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2111552)