A note on M-convex functions on jump systems
Let \(x,y\in \mathbb{Z}^{n}\). A vector \(s\in \mathbb{Z}^{n}\) is said to be an \((x,y)\)-increment if either \(s\) or \(-s\) is one of the \(n\) unit vectors and \(x\wedge y\leq x+s\leq x\vee y\). Let \(f:\mathbb{Z}^{n}\rightarrow \mathbb{R\cup \{+\infty \}}\). One says that \(f\) is jump M-convex if for any \(x,y\in \mathrm{dom}~f\) and any \((x,y)\)-increment \(s\), there exists an \((x+s,y)\)-increment \(t\) such that \(x+s+t,~y-s-t\in \mathrm{dom}~f\) and \(f(x)+f(y)\geq f(x+s+t)+f(y-s-t)\). One says that \(f\) is jump M\(^{\sharp}\)-convex if for any \(x,y\in \mathrm{dom}~f\) and any \((x,y)\)-increment \(s\), one of the following two conditions holds: (i) \(x+s,~y-s\in \mathrm{dom}~f\), and \(f(x)+f(y)\geq f(x+s)+f(y-s)\), (ii) there exists an \((x+s,y)\)-increment \(t\) such that \(x+s+t,~y-s-t\in \mathrm{dom}~f\) and \(f(x)+f(y)\geq f(x+s+t)+f(y-s-t)\). For \(x\in \mathbb{Z}^{n}\), define \(\pi (x)=0\) if the component sum of \(x\) is even and \(\pi (x)=1\) otherwise. The main result states that \(f\) is jump M\(^{\sharp }\)-convex if and only if the function \(\widetilde{f}:\mathbb{Z}^{n+1}\rightarrow \mathbb{R\cup \{+\infty \}}\) defined by \(\widetilde{f}(x_{0},x)=f(x)\) if \(x_{0}=\pi (x)\) and \(\widetilde{f}(x_{0},x)=+\infty \) otherwise is jump M-convex.
- 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
- \(\Delta\)-matroid and jump system
- 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 concavity and the half-plane property
- Discrete Convex Analysis
- 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
- Geometry of jump systems
- Even factors, jump systems, and discrete convexity
- A GREEDY ALGORITHM FOR MINIMIZING A SEPARABLE CONVEX FUNCTION OVER A FINITE JUMP SYSTEM
- scientific article; zbMATH DE number 2147934 (Why is no real title available?)
- A survey of fundamental operations on discrete convex functions of various kinds
- On basic operations related to network induction of discrete convex functions
- 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
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)
