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

DOI10.1007/S13160-022-00512-3zbMATH Open1505.52010arXiv2110.10445OpenAlexW3205990945MaRDI QIDQ2111552FDOQ2111552

Authors: Satoko Moriguchi, Kazuo Murota 

Publication date: 17 January 2023

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

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.

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

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

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)

Cites Work

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

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)