A note on M-convex functions on jump systems

DOI10.1016/J.DAM.2020.09.019MaRDI QIDQ2217499zbMATH OpenOpenAlexFDO

Authors Kazuo Murota

Publication date 29 December 2020

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

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

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)

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.

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

Cites work

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

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
• \(\Delta\)-matroid and jump system
• Geodesic property of greedy algorithms for optimization problems on jump systems and delta-matroids
• Induction of M-convex functions by linking systems
• scientific article; zbMATH DE number 2147934 (Why is no real title available?)
• 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)