Minimization of an M-convex function (Q1392577)

A function \(f : \mathbb{Z}^n \rightarrow \mathbb{R}\cup \{ \infty \}\) is called \(M\)-convex if for any two vectors \(x,y \in\mathbb{Z}^n\), such that \(f(x) , f(y) \neq \infty\), and any unit vector \(e_i\) in a direction where \(x - y\) is positive there is a unit vector \(e_j\) in a direction where \(x-y\) is negative, such that \(f(x) + f(y) \geq f(x-e_i+e_j) +f(y+e_i -e_j)\). This notion was introduced in a series of papers by \textit{K. Murota} [e.g., Adv. Math. 124, No. 2, 272-311, Art. No. 0084 (1996; Zbl 0867.90092)] and provides a common generalization of valuations of matroids as considered by \textit{A. W. M. Dress} and \textit{W. Wenzel} [see, e.g., Adv. Math. 93, No. 2, 214-250 (1992; Zbl 0754.05027)] and of the integral points in the base polyhedron of an integral submodular system considered by \textit{S. Fujishige} [Submodular functions and optimization, Ann. Discrete Math. 47 (1991; Zbl 0728.90056)]. The main result of the paper is the description of a weakly-polynomial time algorithm for minimizing an \(M\)-convex function.