The Shapley–Folkman theorem is a statement about the Minkowski sum of (non-convex) sets, expressing the closeness of the Minkowski sum to convexity in a quantitative manner. This paper establishes similar theorems for integrally convex sets, M -convex sets, and L -convex sets, which are major classes of discrete convex sets in discrete convex analysis.

A binary VCSP is a general framework for the minimization problem of a function represented as the sum of unary and binary cost functions. An important line of VCSP research is to investigate what functions can be solved in polynomial time. Cooper and Živný classified the tractability of binary VCSP instances according to the concept of “triangle,” and showed that the only interesting tractable case is the one induced by the joint winner property (JWP). Recently, Iwamasa, Murota, and Živný made a link between VCSP and discrete convex analysis, showing that a function satisfying the JWP can be transformed into a function represented as the sum of two quadratic M-convex functions, which can be minimized in polynomial time via an M-convex intersection algorithm if the value oracle of each M-convex function is given. In this article, we give an algorithmic answer to a natural question: What binary finite-valued CSP instances can be represented as the sum of two quadratic M-convex functions and can be solved in polynomial time via an M-convex intersection algorithm? We solve this problem by devising a polynomial-time algorithm for obtaining a concrete form of the representation in the representable case. Our result presents a larger tractable class of binary finite-valued CSPs, which properly contains the JWP class.

A binary VCSP is a general framework for the minimization problem of a function represented as the sum of unary and binary cost functions.An important line of VCSP research is to investigate what functions can be solved in polynomial time. Cooper-Zivny classified the tractability of binary VCSP instances according to the concept of "triangle," and showed that the only interesting tractable case is the one induced by the joint winner property (JWP). Recently, Iwamasa-Murota-Zivny made a link between VCSP and discrete convex analysis, showing that a function satisfying the JWP can be transformed into a function represented as the sum of two M-convex functions, which can be minimized in polynomial time via an M-convex intersection algorithm if the value oracle of each M-convex function is given. In this paper, we give an algorithmic answer to a natural question: What binary finite-valued CSP instances can be solved in polynomial time via an M-convex intersection algorithm? We solve this problem by devising a polynomial-time algorithm for obtaining a concrete form of the representation in the representable case. Our result presents a larger tractable class of binary finite-valued CSPs, which properly contains the JWP class.

In discrete convex analysis, the scaling and proximity properties for the class of L^natural-convex functions were established more than a decade ago and have been used to design efficient minimization algorithms. For the larger class of integrally convex functions of n variables, we show here that the scaling property only holds when n leq 2, while a proximity theorem can be established for any n, but only with an exponential bound. This is, however, sufficient to extend the classical logarithmic complexity result for minimizing a discretely convex function in one dimension to the case of integrally convex functions in two dimensions. Furthermore, we identified a new class of discrete convex functions, called directed integrally convex functions, which is strictly between the classes of L^natural -convex and integrally convex functions but enjoys the same scaling and proximity properties that hold for L^natural -convex functions.

A jump system is a set of integer points with an exchange property, which is a generalization of a matroid, a delta‐matroid, and a base polyhedron of an integral polymatroid (or a submodular system). Recently, the concept of M‐convex functions on constant‐parity jump systems was introduced by Murota as a class of discrete convex functions that admit a local criterion for global minimality. M‐convex functions on constant‐parity jump systems generalize valuated matroids, valuated delta‐matroids, and M‐convex functions on base polyhedra. This paper reveals that the class of M‐convex functions on constant‐parity jump systems is closed under a number of natural operations such as splitting, aggregation, convolution, composition, and transformation by networks. The present results generalize hitherto‐known similar constructions for matroids, delta‐matroids, valuated matroids, valuated delta‐matroids, and M‐convex functions on base polyhedra.

The concept of M-convex functions is generalized for functions defined on constant-parity jump systems. M-convex functions arise from minimumweight perfect b-matchings and from a separable convex function (sum of univariate convex functions) on the degree sequences of an undirected graph. As a generalization of a recent result of Apollonio and Sebo for the minsquare factor problem, a local optimality criterion is given for minimization of an M-convex function subject to a component sum constraint.

A matrix $A = \begin{pmatrix} Q \\ T \end{pmatrix}$ is called a layered mixed matrix (LM-matrix) if the set of nonzero entries of T is algebraically independent over the field to which the entries of Q belong. This concept has been proposed as a mathematical tool for describing discrete physical/engineering systems. It is known that there uniquely exists a finest block-triangularization of an LM-matrix, which is called the combinatorial canonical form (CCF). In this paper, associated with an LM-matrix we introduce a new submodular function q characterizing its rank. This submodular function q is defined on a modular lattice. It will be shown that the principal structure of q gives the coarsest decomposition of the row side that is finer than any decomposition induced by the CCF of the submatrix consisting of a base of the column vectors of A. This gives a best possible bound on the extent to which the whole system can be decomposed by a suitable choice of design variables.

The independent assignment problem (or the weighted matroid intersection problem) is extended using Dress and Wenzel’s matroid valuations, which are attached to the vertex set of the underlying bipartite graph as an additional weighting. Specifically, the problem considered is as follows: given a bipartite graph $G = (V^ + ,V^ - ;A)$ with arc weight $w:A \to \mathbf{R}$ and matroid valuations $\omega ^ + $ and $\omega^ - $ on $V^ + $ and $V^ - $ respectively, find a matching $M( \subseteq A)$ that maximizes $\sum \{ \omega (a) \mid a \in M\} + \omega^ + (\partial ^ + M) + \omega^ - (\partial ^ - M)$, where $\partial ^ + M$ and $\partial ^ - M$ denote the sets of vertices in $V^ + $ and $V^ - $ incident to M. As natural extensions of the previous results for the independent assignment problem, two optimality criteria are established: one in terms of potentials and the other in terms of negative cycles in an auxiliary graph.

Based on the optimality criteria established in part I [SIAM J. Discrete Math., 9 (1996), pp. 545–561] we show a primal-type cycle-canceling algorithm and a primal–dual-type augmenting algorithm for the valuated independent assignment problem: given a bipartite graph $G = (V^ + ,V^ - ;A)$ with arc weight $w:A \to \mathbf{R}$ and matroid valuations $\omega^ + $ and $\omega ^ - $ on $V^ + $ and $V^ - $, respectively; find a matching $M( \subseteq A)$ that maximizes $\sum \{ w(a)\mid a \in M\} + \omega^ + (\partial ^ + M) + \omega^ - (\partial ^ - M)$, where $\partial ^ + M$ and $\partial ^ - M$ denote the sets of vertices in $V^ + $ and $V^ - $ incident to M. The proposed algorithms generalize the previous algorithms for the independent assignment problem as well as for the weighted matroid intersection problem, including those due to Lawler [Math. Prog., 9 (1975), pp. 31–56], Ini and Tomizawa [J. Oper. Res. Soc. Japan, 19 (1976), pp. 32–57], Fujishige [J. Oper. Res. Soc. Japan, 20 (1977), pp. 1–15], Frank [J. Algorithms, 2 (1981), pp. 328–336], and Zimmermann [Discrete Appl. Math., 36 (1992), pp. 179–189].

Let $A(x) = (A_{ij} (x))$ be a square matrix with $A_{ij}$ being a polynomial in x. This paper proposes “combinatorial relaxation-” type algorithms for computing the degree of the determinant $\delta (A) = \deg_{x} \det A(x)$ based on its combinatorial upper bound $\widehat{\delta}(A)$, which is defined in terms of the maximum weight of a perfect matching in an associated graph. The graph is bipartite for a general square matrix A and nonbipartite for a skew-symmetric A. The algorithm transforms A to another matrix $A^{\prime}$, for which $\delta (A) = \delta (A^{\prime}) = \widehat{\delta}(A^{\prime})$ with successive elementary operations. The algorithm is efficient, making full use of the fast algorithms for weighted matchings; it is combinatorial in almost all cases (or generically) and invokes algebraic elimination routines only when accidental numerical cancellations occur. It is shown in passing that for a (skew-)symmetric polynomial matrix $A(x)$ there exists a unimodular matrix $U(x)$ such that $A'(x) = U(x)A(x)U(x)^{\text{T}}$ satisfies $\delta (A) = \delta (A^{\prime}) = \widehat{\delta}(A^{\prime})$.

Let $A(t,x) = (A_{ij} (t,x))$ be a square matrix with $A_{ij}$ being a polynomial in t and x. This paper proposes an algorithm for computing the Puiseux (= fractional power) series solutions $x = x(t)$ to the equation ${\operatorname{det}}A(t, x) = 0$. The algorithm is based on an observation which links the Newton diagram (polygon) for det ${\operatorname{det}}A(t, x)$ with the perfect matchings of a bipartite graph associated with A. The algorithm is efficient, making full use of available fast network-type algorithms.

We extend the concept of Voronoi diagram in the ordinary Euclidean geometry for n points to the one in the Laguerre geometry for n circles in the plane, where the distance between a circle and a point is defined by the length of the tangent line, and show that there is an $O(n\log n)$ algorithm for this extended case. The Voronoi diagram in the Laguerre geometry may be applied to solving effectively a number of geometrical problems such as those of determining whether or not a point belongs to the union of n circles, of finding the connected components of n circles, and of finding the contour of the union of n circles. As in the case with ordinary Voronoi diagrams, the algorithms proposed here for those problems are optimal to within a constant factor. Some extensions of the problem and the algorithm from different viewpoints are also suggested.

Abstract Several linear‐time approximation algorithms for the minimum‐weight perfect matching in a plane are proposed, and their worst‐ and average‐case behaviors are analyzed theoretically as well as experimentally. A linear‐time approximation algorithm, named the “spiral‐rack algorithm (with preprocess and with tour),” is recommended for practical purposes. This algorithm is successfully applied to the drawing of road maps such as that of the Tokyo city area.