Satoko Moriguchi
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
Research Subjects
Satoko Moriguchi has a total of 10 co-authors. Here are the top co-authors by number of shared publications:
- Kazuo Murota
The Institute of Statistical Mathematics, Tachikawa, Japan
10 shared publications - Akihisa Tamura
Department of Mathematics, Keio University, Yokohama, Japan
4 shared publications - Fabio Tardella
Department of Information Engineering, University of Florence, Florence, Italy
4 shared publications Hidenori Tsuji
School of Industrial Technology, Advanced Institute of Industrial Technology, Shinagawa, Tokyo, Japan
1 shared publication- Kazunori Okada
San Francisco State Univ. (USA)
1 shared publication Masahiko Narita
School of Industrial Technology, Advanced Institute of Industrial Technology, Shinagawa, Tokyo, Japan
1 shared publication
Latest Publications
- Open Access
Inclusion and Intersection Relations Between Fundamental Classes of Discrete Convex Functions
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 AccessInclusion and Intersection Relations Between Fundamental Classes of Discrete Convex Functions
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
- 11 June 2022
- Published by Springer Nature in Japan Journal of Industrial and Applied Mathematics
- Vol. 40 (1) , 223-263
Note on the polyhedral description of the Minkowski sum of two L-convex sets
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}$$ -convex sets, is an intriguing object that is closely related to polymatroid intersection. This paper reveals the polyhedral description of an L $$_{2}$$ -convex set, together with the observation that the convex hull of an L $$_{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.- 11 June 2022
- Published by Springer Nature in Japan Journal of Industrial and Applied Mathematics
- Vol. 40 (1) , 223-263
Open AccessNote on the polyhedral description of the Minkowski sum of two L-convex sets
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}$$ -convex sets, is an intriguing object that is closely related to polymatroid intersection. This paper reveals the polyhedral description of an L $$_{2}$$ -convex set, together with the observation that the convex hull of an L $$_{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
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.
Open AccessNote on the Polyhedral Description of the Minkowski Sum of Two L-convex Sets
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.
- 1 February 2020
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in Mathematics of Operations Research
- Vol. 45 (1) , 99-128
Discrete Midpoint Convexity
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.
- 1 February 2020
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in Mathematics of Operations Research
- Vol. 45 (1) , 99-128
Discrete Midpoint Convexity
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
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 AccessOn Fundamental Operations for Multimodular Functions
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
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 AccessDiscrete Midpoint Convexity
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.
- 1 February 2019
- Published by Elsevier in Discrete Applied Mathematics
- Vol. 255, 283-298
Projection and convolution operations for integrally convex functions
- 1 February 2019
- Published by Elsevier in Discrete Applied Mathematics
- Vol. 255, 283-298
Projection and convolution operations for integrally convex functions
- Open Access
Projection and Convolution Operations for Integrally Convex Functions
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.
Open AccessProjection and Convolution Operations for Integrally Convex Functions
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.
- 24 January 2018
- Published by Springer Nature in Mathematical Programming
- Vol. 175 (1-2) , 119-154
Scaling, proximity, and optimization of integrally convex functions
- 24 January 2018
- Published by Springer Nature in Mathematical Programming
- Vol. 175 (1-2) , 119-154
Scaling, proximity, and optimization of integrally convex functions
- Open Access
Scaling, Proximity, and Optimization of Integrally Convex Functions
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.Open AccessScaling, Proximity, and Optimization of Integrally Convex Functions
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.