A note on M-convex functions on jump systems

DOI10.1016/J.DAM.2020.09.019zbMATH Open1475.05024arXiv1907.06209OpenAlexW3090411163MaRDI QIDQ2217499FDOQ2217499

Authors: Kazuo Murota 

Publication date: 29 December 2020

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Abstract: A jump system is defined as a set of integer points (vectors) with a certain exchange property, generalizing the concepts of matroids, delta-matroids, and base polyhedra of integral polymatroids (or submodular systems). A discrete convexity concept is defined for functions on constant-parity jump systems and it has been used in graph theory and algebra. In this paper we call it "jump M-convexity" and extend it to "jump M-natural-convexity" for functions defined on a larger class of jump systems. By definition, every jump M-convex function is a jump M-natural-convex function, and we show the equivalence of these concepts by establishing an (injective) embedding of jump M-natural-convex functions in n variables into the set of jump M-convex functions in n+1 variables. Using this equivalence we show further that jump M-natural-convex functions admit a number of natural operations such as aggregation, projection (partial minimization), convolution, composition, and transformation by a network.

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

Recommendations

• Operations on M‐Convex Functions on Jump Systems
• M-Convex Functions on Jump Systems: A General Framework for Minsquare Graph Factor Problem
• Polynomial-Time Algorithms for Linear and Convex Optimization on Jump Systems
• Minimization of an M-convex function
• \(M\)-convex function on generalized polymatroid

zbMATH Keywords

jump systemdiscrete convex analysisM-convex function

Mathematics Subject Classification ID

Matroids in convex geometry (realizations in the context of convex polytopes, convexity in combinatorial structures, etc.) (52B40) Combinatorial aspects of matroids and geometric lattices (05B35) Convexity of real functions of several variables, generalizations (26B25)

Cites Work

• Discrete Convex Analysis
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Submodular functions and optimization.
• Minconvex Factors of Prescribed Size in Graphs
• Delta-Matroids, Jump Systems, and Bisubmodular Polyhedra
• Greedy algorithm and symmetric matroids
• The membership problem in jump systems
• Even factors, jump systems, and discrete convexity
• Polynomial-Time Algorithms for Linear and Convex Optimization on Jump Systems
• An algorithm for \((n-3)\)-connectivity augmentation problem: jump system approach
• A proof of Cunningham's conjecture on restricted subgraphs and jump systems
• Operations on M‐Convex Functions on Jump Systems
• M-Convex Functions on Jump Systems: A General Framework for Minsquare Graph Factor Problem
• Integer Programming and Combinatorial Optimization
• Pseudomatroids
• A greedy-algorithm characterization of valuated \(\Delta\)-matroids
• Some combinatorial properties of discriminants in metric vector spaces
• \(\Delta\)-matroid and jump system
• Induction of M-convex functions by linking systems
• Optimal matching forests and valuated delta-matroids
• Discrete concavity and the half-plane property

Cited In (10)

• Operations on M‐Convex Functions on Jump Systems
• M-Convex Functions on Jump Systems: A General Framework for Minsquare Graph Factor Problem
• Geodesic property of greedy algorithms for optimization problems on jump systems and delta-matroids
• \(\Delta\)-matroid and jump system
• Induction of M-convex functions by linking systems
• Title not available (Why is that?)
• Even factors, jump systems, and discrete convexity
• Geometry of jump systems
• On basic operations related to network induction of discrete convex functions
• A survey of fundamental operations on discrete convex functions of various kinds

This page was built for publication: A note on M-convex functions on jump systems

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