A note on M-convex functions on jump systems

DOI10.1016/j.dam.2020.09.019zbMath1475.05024arXiv1907.06209OpenAlexW3090411163MaRDI QIDQ2217499

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)

Related Items

Geodesic property of greedy algorithms for optimization problems on jump systems and delta-matroids, A survey of fundamental operations on discrete convex functions of various kinds, On basic operations related to network induction of discrete convex functions

Cites Work

• An algorithm for \((n-3)\)-connectivity augmentation problem: jump system approach
• A proof of Cunningham's conjecture on restricted subgraphs and jump systems
• \(\Delta\)-matroid and jump system
• Induction of M-convex functions by linking systems
• Some combinatorial properties of discriminants in metric vector spaces
• Pseudomatroids
• A greedy-algorithm characterization of valuated \(\Delta\)-matroids
• The membership problem in jump systems
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Even factors, jump systems, and discrete convexity
• Submodular functions and optimization.
• Discrete Concavity and the Half-Plane Property
• Polynomial-Time Algorithms for Linear and Convex Optimization on Jump Systems
• Minconvex Factors of Prescribed Size in Graphs
• Greedy algorithm and symmetric matroids
• Discrete Convex Analysis
• Delta-Matroids, Jump Systems, and Bisubmodular Polyhedra
• Optimal Matching Forests and Valuated Delta-Matroids
• 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