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

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

Kazuo Murota, Satoko Moriguchi

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

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
• 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 (1)

• Recent progress on integrally convex functions

   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 👍 👎

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)