August 5, 2023

Errata and Supplements toDiscrete Convex Analysis (SIAM, 2003)
2nd printing (soft cover), 2013, ISBN 978-1-611972-55-9• Page 77, line 2 from bottom:+∞ ≤ +∞• Page 94, line 4 from bottom:

Delete “is as follows.”=⇒+∞ ≥ +∞• Page 113, line 12 from bottom (last paragraph of the proof of Theorem 4.18):
Let p be such that the optimal solutions to (A) with respect to p form a minimal
face of the feasible region of (A).
• Page 117, line 1 (below Figure 4.1):
Q ⊆ ZV is an M♮ -convex set =⇒ Q ⊆ ZV is said to be an M♮ -convex set• Page 139, Proposition 6.8 (2):(6.26) is redundant.

Condition (6.26) follows from (6.27), and hence• Page 143, three lines above Theorem 6.13:
f[a,b] for an integer interval [a, b] =⇒f[a,b] for the restriction of f to an integer interval [a, b]• Page 143, Theorem 6.13 (8) [Convolution of M-convex functions]
The proof here makes use of transformation by a network, but an alternative direct
proof can be found in:K. Murota: On infimal convolution of M-convex functions, RIMS Kokyuroku, No.1371(2004), 20–26.
• Page 151, Theorem 6.30, Proof of Claim 1:
The final step reads: “This shows (B-EXC+ [R]) for B. Therefore, B is an Mconvex set.” Before we can argue in this way, we have to verify B ∩ ZV = B, whichis possible.
• Page 152, Section 6.8:
A characterization of gross substitutes property in termsof an exchange property is also found in:
H. Reijnierse, A. van Gallekom, and J. A. M. Potters: Verifying gross substitutability, Economic Theory, 20 (2002), 767–776.
• Page 172, Proof of Theorem 6.74:“Theorem 6.4 can be strengthened to a statement that (M-EXC[Z]) and (M-EXCloc [Z])are equivalent if dom f satisfies (Q-EXCw ). (This can be shown by modifying theproof of Claim 2 in the proof of Theorem 6.4.)”
The detail of the argument can be found in a memorandum of A. Shioura: Levelset characterization of M-convex functions (February 1998); see Claim 2 on page 6.
1

• Page 185, Theorem 7.14 [L-optimality criterion]
The proof here makes use of the optimality criterion for integrally convex functions,but an alternative direct proof can be found in:
K: Murota: A proof of the L-optimality criterion theorem, unpublished note, July
2004,
https://kzmurota.fpark.tmu.ac.jp/paper/loptimality04.pdf• Page 186, Theorem 7.17
“with a bounded nonempty eﬀective domain”=⇒ “that is convex-extensible or has a bounded nonempty eﬀective domain”
For an L-convex function g, the boundedness assumption on the eﬀective domain
is intended to mean the boundedness of dom g intersected with a coordinate plane{p | p(v) = 0} for some v ∈ V . Note that the eﬀective domain of an L-convex
function has the invariance in the direction of 1.
• Page 219, Theorem 8.17 [M-convex intersection theorem]
The proof here makes use of the M-separation theorem, but an alternative direct
proof can be found in:K. Murota: A proof of the M-convex intersection theorem, RIMS Kokyuroku,No.1371 (2004), 13–19.
• Page 228, line 5, Theorem 8.33: f2 (x + χui+1 − χvi )=⇒f2 (x − χui+1 + χvi )• Page 228, line 13, Theorem 8.34:
f2 (xα + α(χui+1 − χvi )) =⇒ f2 (xα − α(χui+1 − χvi ))• Page 231, Proof of Theorem 8.42:
There was a confusion between L2 -convexity and L♮2 -convexity. Please change thefirst paragraph of the proof (“It suﬃces to consider ..... found in Murota–Shioura[153].”) to the following text:
To emphasize the essence we give a proof for the integral convexity ofan L2 -convex set, from which the integral convexity of an L♮2 -convex set
follows. This implies, by Theorem 3.29, the integral convexity of an L♮2 convex function g with a bounded eﬀective domain, since arg min g[−x] isan L♮2 -convex set for any x ∈ RV by Proposition 8.40. A complete proof
can be found in Murota–Shioura [153].
Integral convexity of an L♮2 -convex set (L2 -convex set) also follows from its boxtotal dual integrality (see Theorem 5.1 of S. Moriguchi and K. Murota: Noteon the polyhedral description of the Minkowski sum of two L-convex sets, Japan
Journal of Industrial and Applied Mathematics, Vol.40 (2023), No.1, 223–263.
https://doi.org/10.1007/s13160-022-00512-3 (Open access))• Page 305, Section 10.3.1:
A detailed analysis of the steepest descent algorithm for L-convex functions can befound in:2

K. Murota and A. Shioura: Exact bounds for steepest descent algorithms of Lconvex function minimization, Operations Research Letters, 42 (2014), 361–366.
• Page 331, (−M♮ -SWGS[Z]):For x ∈ arg min U [−p]=⇒For x ∈ arg max U [−p]• Page 333, “(SNC) for Ũ =⇒ M♮ -concavity for U ”:
The converse of this statement is also true, that is,(SNC) for Ũ ⇐⇒ M♮ -concavity for U
holds. See K. Murota: Multiple exchange property for M♮ -concave functions andvaluated matroids, Mathematics of Operations Research, 43 (2018), 781-788.
https://doi.org/10.1287/moor.2017.0882 , arXiv: http://arxiv.org/abs/1608.07021• Page 365, [39]:P. G. Doyle and J. L. Snell: Random Walks and Electrical Networks, Mathematical Association of America, Washington DC, 1984.
• Page 369, [105] (S. Iwata and M. Shigeno):(2003)• Page 372, [143] (K. Murota):(1999)=⇒(1998)• Page 375, [192] (A. Shioura):(2003)=⇒(2004)• Page 376, [202]:

D. M. Topkis,=⇒=⇒(2002)D. M. Topkis:

Updates of bib-infor:• [33] V. Danilov, G. Koshevoy, and C. Lang: Gross substitution, discrete convexity,and submodularity, Discrete Applied Mathematics, 131 (2003), 283–298.
• [47] A. Eguchi and S. Fujishige: An extension of the Gale–Shapley stable matchingalgorithm to a pair of M♮ -concave functions, Discrete Mathematics and Systems
Science Research Report, No. 02-05, Division of Systems Science, Osaka University,
November 2002. (This is the final form; no journal paper exists.)• [69] S. Fujishige and Z. Yang: A note on Kelso and Crawford’s gross substitutes
condition, Mathematics of Operations Research, 28 (2003), 463–469.
(end)

3