SMSatoko Moriguchi

Satoko Moriguchi

*This is an algorithmically generated author record based on publicly available information.

Current Organizations / Institutes

The organizations/institutes from the scholar's latest article

Previous Organizations / Institutes

The organizations / institutes from the scholar's other articles in the past ten years


Satoko Moriguchi has a total of 10 co-authors. Here are the top co-authors by number of shared publications:


Latest Publications

  • Open Access

    Inclusion and Intersection Relations Between Fundamental Classes of Discrete Convex Functions

    by Satoko Moriguchi, Kazuo Murota

    In discrete convex analysis, various convexity concepts are considered for discrete functions such as separable convexity, L-convexity, M-convexity, integral convexity, and multimodularity. These concepts of discrete convex functions are not mutually independent. For example, M-natural-convexity is a special case of integral convexity, and the combination of L-natural-convexity and M-natural-convexity coincides with separable convexity. This paper aims at a fairly comprehensive analysis of the inclusion and intersection relations for various classes of discrete convex functions. Emphasis is put on the analysis of multimodularity in relation to L-natural-convexity and M-natural-convexity.

  • Open Access

    Note on the polyhedral description of the Minkowski sum of two L-convex sets

    by Satoko Moriguchi, Kazuo Murota

    L-convex sets are one of the most fundamental concepts in discrete convex analysis. Furthermore, the Minkowski sum of two L-convex sets, called L $$_{2}$$ 2 -convex sets, is an intriguing object that is closely related to polymatroid intersection. This paper reveals the polyhedral description of an L $$_{2}$$ 2 -convex set, together with the observation that the convex hull of an L $$_{2}$$ 2 -convex set is a box-TDI polyhedron. Two different proofs are given for the polyhedral description. The first is a structural short proof, relying on the conjugacy theorem in discrete convex analysis, and the second is a direct algebraic proof, based on Fourier–Motzkin elimination. The obtained results admit natural graph representations. Implications of the obtained results in discrete convex analysis are also discussed.


  • Open Access

    Note on the Polyhedral Description of the Minkowski Sum of Two L-convex Sets

    by Satoko Moriguchi, Kazuo Murota

    L-convex sets are one of the most fundamental concepts in discrete convex analysis. Furthermore, the Minkowski sum of two L-convex sets, called L2-convex sets, is an intriguing object that is closely related to polymatroid intersection. This paper reveals the polyhedral description of an L2-convex set, together with the observation that the convex hull of an L2-convex set is a box-TDI polyhedron. Two different proofs are given for the polyhedral description. The first is a structural short proof, relying on the conjugacy theorem in discrete convex analysis, and the second is a direct algebraic proof, based on Fourier-Motzkin elimination. The obtained results admit natural graph representations. Implications of the obtained results in discrete convex analysis are also discussed.

  • Discrete Midpoint Convexity

    by Satoko Moriguchi, Kazuo Murota, Akihisa Tamura, Fabio Tardella

    For a function defined on the integer lattice, we consider discrete versions of midpoint convexity, which offer a unifying framework for discrete convexity of functions, including integral convexity, L♮-convexity, and submodularity. By considering discrete midpoint convexity for all pairs at ℓ∞-distance equal to 2 or not smaller than 2, we identify new classes of discrete convex functions, called locally and globally discrete midpoint convex functions. These functions enjoy nice structural properties. They are stable under scaling and addition and satisfy a family of inequalities named parallelogram inequalities. Furthermore, they admit a proximity theorem with the same small proximity bound as that for L♮-convex functions. These structural properties allow us to develop an algorithm for the minimization of locally and globally discrete midpoint convex functions based on the proximity-scaling approach and on a novel 2-neighborhood steepest descent algorithm.


  • Open Access

    On Fundamental Operations for Multimodular Functions

    by Satoko Moriguchi, Kazuo Murota

    Multimodular functions, primarily used in the literature of queueing theory, discrete-event systems, and operations research, constitute a fundamental function class in discrete convex analysis. The objective of this paper is to clarify the properties of multimodular functions with respect to fundamental operations such as permutation and scaling of variables, projection (partial minimization) and convolution. It is shown, in particular, that the class of multimodular functions is stable under projection under a certain natural condition on the variables to be minimized, and the convolution of two multimodular functions is not necessarily multimodular, even in the special case of the convolution of a multimodular function with a separable convex function.

  • Open Access

    Discrete Midpoint Convexity

    by Satoko Moriguchi, Kazuo Murota, Akihisa Tamura, Fabio Tardella

    For a function defined on a convex set in a Euclidean space, midpoint convexity is the property requiring that the value of the function at the midpoint of any line segment is not greater than the average of its values at the endpoints of the line segment. Midpoint convexity is a well-known characterization of ordinary convexity under very mild assumptions. For a function defined on the integer lattice, we consider the analogous notion of discrete midpoint convexity, a discrete version of midpoint convexity where the value of the function at the (possibly noninteger) midpoint is replaced by the average of the function values at the integer round-up and round-down of the midpoint. It is known that discrete midpoint convexity on all line segments with integer endpoints characterizes L$^{\natural}$-convexity, and that it characterizes submodularity if we restrict the endpoints of the line segments to be at $\ell_\infty$-distance one. By considering discrete midpoint convexity for all pairs at $\ell_\infty$-distance equal to two or not smaller than two, we identify new classes of discrete convex functions, called local and global discrete midpoint convex functions, which are strictly between the classes of L$^{\natural}$-convex and integrally convex functions, and are shown to be stable under scaling and addition. Furthermore, a proximity theorem, with the same small proximity bound as that for L$^{\natural}$-convex functions, is established for discrete midpoint convex functions. Relevant examples of classes of local and global discrete midpoint convex functions are provided.

  • Open Access

    Projection and Convolution Operations for Integrally Convex Functions

    by Satoko Moriguchi, Kazuo Murota

    This paper considers projection and convolution operations for integrally convex functions, which constitute a fundamental function class in discrete convex analysis. It is shown that the class of integrally convex functions is stable under projection, and this is also the case with the subclasses of integrally convex functions satisfying local or global discrete midpoint convexity. As is known in the literature, the convolution of two integrally convex functions may possibly fail to be integrally convex. We show that the convolution of an integrally convex function with a separable convex function remains integrally convex. We also point out in terms of examples that the similar statement is false for integrally convex functions with local or global discrete midpoint convexity.

  • Scaling, proximity, and optimization of integrally convex functions

    by Satoko Moriguchi, Kazuo Murota, Akihisa Tamura, Fabio Tardella


  • Open Access

    Scaling, Proximity, and Optimization of Integrally Convex Functions

    by Satoko Moriguchi, Kazuo Murota, Akihisa Tamura, Fabio Tardella

    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 a superexponential bound. This is, however, sufficient to extend the classical logarithmic complexity result for minimizing a discrete convex function of one variable to the case of integrally convex functions of any fixed number of variables.