August 5, 2023

Errata and Supplements toDiscrete Convex Analysis (SIAM, 2003)
1st printing (hard cover) (ISBN 0-89871-540-7)• Page 77, line 2 from bottom:+∞ ≤ +∞• Page 94, line 4 from bottom:

Delete “is as follows.”• Page 109, line 12:

4 min(λj , λk ) (≥ 4/N )=⇒=⇒+∞ ≥ +∞

2 min(λj , λk ) (≥ 2/N )• 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 133, (6.2):∆f (z, v, u)• Page 139, Proposition 6.8 (2):(6.26) is redundant.

=⇒ ∆f (z; v, u)
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.

1

• 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.
• 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].

2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: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 Uholds. 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:• [32] V. I. Danilov and G. A. Koshevoy: Discrete convexity and unimodularity, I,Advances in Mathematics, 189 (2004), 301–324.
• [33] V. Danilov, G. Koshevoy, and C. Lang: Gross substitution, discrete convexity,and submodularity, Discrete Applied Mathematics, 131 (2003), 283–298.
• [44] J. Edmonds: Submodular functions, matroids and certain polyhedra, in: R.
Guy, H. Hanani, N. Sauer, and J. Schönheim, eds., Combinatorial Structures andTheir Applications, Gordon and Breach, New York, 1970, 69–87. Also in: M.
Jünger, G. Reinelt, G. Rinaldi, eds., Combinatorial Optimization—Eureka, YouShrink!, Lecture Notes in Computer Science, 2570, Springer-Verlag, Berlin, 2003,
11–26.
3

• [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.)• [53] L. R. Ford, Jr., and D. R. Fulkerson: Flows in Networks, Princeton UniversityPress, Princeton, 1962.
• [65] S. Fujishige: Submodular Functions and Optimization, Annals of Discrete
Mathematics, 47, North-Holland, Amsterdam, 1991; 2nd ed., Annals of Discrete
Mathematics, 58, Elsevier, 2005.
• [67] S. Fujishige, K. Makino, T. Takabatake, and K. Kashiwabara: Polybasic polyhedra: structure of polyhedra with edge vectors of support size at most 2, DiscreteMathematics, 280 (2004), 13–27.
• [69] S. Fujishige and Z. Yang: A note on Kelso and Crawford’s gross substitutes
condition, Mathematics of Operations Research, 28 (2003), 463–469.
• [70] S. Fujishige and X. Zhang: New algorithms for the intersection problem of submodular systems, Japan Journal of Industrial and Applied Mathematics, 9 (1992),369–382.
• [75] J. F. Geelen and S. Iwata: Matroid matching via mixed skew-symmetric matrices, Combinatorica, 25 (2005), 187–215.
• [76] J. F. Geelen, S. Iwata, and K. Murota: The linear delta-matroid parity problem,
Journal of Combinatorial Theory (B), 88 (2003), 377–398.
• [100] S. Iwata: A faster scaling algorithm for minimizing submodular functions,
in: W. J. Cook and A. S. Schulz, eds., Integer Programming and Combinatorial
Optimization, Lecture Notes in Computer Science, 2337, Springer-Verlag, 2002,
1–8; SIAM Journal on Computing, 32 (2003), 833–840.
• [103] S. Iwata, S. T. McCormick, and M. Shigeno: Fast cycle canceling algorithms
for minimum cost submodular flow, Combinatorica, 23 (2003), 503–525.
• [115] B. Korte and J. Vygen: Combinatorial Optimization: Theory and Algorithms,Springer-Verlag, Berlin, 2000; 2nd ed., 2001; 3rd ed., 2006; 4th ed., 2008; 5th ed.,2012.
• [127] S. T. McCormick: Submodular Function Minimization, in: K. Aardal, G.
Nemhauser, and R. Weismantel, eds., Discrete Optimization, Handbooks in Operations Research and Management Science, Vol.12, Elsevier Science Publishers, Berlin,
2006, Chapter 7, 321–391.
• [132] S. Moriguchi and K. Murota: Capacity scaling algorithm for scalable Mconvex submodular flow problems, Optimization Methods and Software, 18 (2003),
207–218.
4• [134] S. Moriguchi and A. Shioura: On Hochbaum’s proximity-scaling algorithm
for the general resource allocation problem, Mathematics of Operations Research,
29 (2004), 394–397.
• [148] K. Murota: On steepest descent algorithms for discrete convex functions,
SIAM Journal on Optimization, 14 (2003), 699–707.
• [155] K. Murota and A. Shioura: Quadratic M-convex and L-convex functions,
Advances in Applied Mathematics, 33 (2004), 318–341.
• [156] should be changed to:K. Murota and A. Shioura: Fundamental properties of M-convex and L-convex functions in continuous variables, IEICE Transactions on Fundamentals of Electronics,Communications and Computer Sciences, E87-A (2004), 1042–1052.
• [157] K. Murota and A. Shioura: Conjugacy relationship between M-convex and Lconvex functions in continuous variables, Mathematical Programming, 101 (2004),415–433.
• [158] K. Murota and A. Shioura: Substitutes and complements in network flows
viewed as discrete convexity, Discrete Optimization, 2 (2005), 256–268.
• [160] K. Murota and A. Tamura: New characterizations of M-convex functions
and their applications to economic equilibrium models with indivisibilities, Discrete
Applied Mathematics, 131 (2003), 495–512.
• [161] K. Murota and A. Tamura: Application of M-convex submodular flow problem
to mathematical economics, in: P. Eades and T. Takaoka, eds., Algorithms andComputation, Lecture Notes in Computer Science, 2223, Springer-Verlag, 2001,
14–25; Japan Journal of Industrial and Applied Mathematics, 20 (2003), 257–277.
• [162] K. Murota and A. Tamura: Proximity theorems of discrete convex functions,
Mathematical Programming, 99 (2004), 539–562.
• [192] A. Shioura: Fast scaling algorithms for M-convex function minimization withapplication to the resource allocation problem, Discrete Applied Mathematics, 134(2003), 303–316.
• [197] A. Tamura: Coordinatewise domain scaling algorithm for M-convex function
minimization, in: W. J. Cook and A. S. Schulz, eds., Integer Programming andCombinatorial Optimization, Lecture Notes in Computer Science, 2337, SpringerVerlag, 2002, 21–35; Mathematical Programming, 102 (2005), 339–354.
• [198] A. Tamura: On convolution of L-convex functions, Optimization Methods andSoftware, 18 (2003), 231–245.
• [208] J. Vygen: A note on Schrijver’s submodular function minimization algorithm,Journal of Combinatorial Theory (B), 88 (2003), 399–402.

5

Addition to Bibliography for 2nd Printing (soft cover)[223] E. Altman, B. Gaujal, and A. Hordijk: Discrete-Event Control of Stochastic
Networks: Multimodularity and Regularity, Lecture Notes in Mathematics, 1829,
Springer-Verlag, Heidelberg, 2003.
[224] S. Fujishige and A. Tamura: A general two-sided matching market with discreteconcave utility functions, Discrete Applied Mathematics, 154 (2006), 950–970.
[225] S. Fujishige and A. Tamura: A two-sided discrete-concave market with possibly
bounded side payments: An approach by discrete convex analysis, Mathematics ofOperations Research, 32 (2007), 136–155.
[226] H. Hirai: A geometric study of the split decomposition, Discrete and ComputationalGeometry, 36 (2006), 331–361.
[227] H. Hirai and K. Murota: M-convex functions and tree metrics, Japan Journal ofIndustrial and Applied Mathematics, 21 (2004), 391–403.
[228] W. T. Huh and G. Janakiraman: On the optimal policy structure in serial inventory
systems with lost sales, Operations Research, 58 (2010), 486–491.
[229] T. Iimura, K. Murota, and A. Tamura: Discrete fixed point theorem reconsidered,
Journal of Mathematical Economics, 41 (2005), 1030–1036.
[230] S. Iwata, S. Moriguchi, and K. Murota: A capacity scaling algorithm for M-convex
submodular flow, Mathematical Programming, 103 (2005), 181–202.
[231] Y. Kobayashi and K. Murota: Induction of M-convex functions by linking systems,
Discrete Applied Mathematics, 155 (2007), 1471–1480.
[232] Y. Kobayashi, K. Murota and K. Tanaka: Operations on M-convex functions on
jump systems, SIAM Journal on Discrete Mathematics, 21 (2007), 107–129.
[233] V. Kolmogorov and A. Shioura: New algorithms for convex cost tension problem
with application to computer vision, Discrete Optimization, 6 (2009), 378–393.
[234] B. Lehmann, D. Lehmann, and N. Nisan: Combinatorial auctions with decreasing
marginal utilities, Games and Economic Behavior, 55 (2006), 270–296.
[235] S. Moriguchi and K. Murota: Discrete Hessian matrix for L-convex functions, IEICE Transactions on Fundamentals of Electronics, Communications and Computer
Sciences, E88-A (2005), 1104–1108.
[236] S. Moriguchi and K. Murota: On discrete Hessian matrix and convex extensibility,
Journal of Operations Research Society of Japan, 55 (2012), 48–62.
[237] S. Moriguchi, A. Shioura and N. Tsuchimura: M-convex function minimization bycontinuous relaxation approach—Proximity theorem and algorithm, SIAM Journal
on Optimization, 21 (2011), 633–668.
[238] K. Murota: Note on multimodularity and L-convexity, Mathematics of Operations
Research, 30 (2005), 658–661.

6

[239] K. Murota: M-convex functions on jump systems: A general framework for minsquare graph factor problem, SIAM Journal on Discrete Mathematics, 20 (2006),
213–226.
[240] K. Murota: Recent developments in discrete convex analysis, in: W. Cook, L. Lovasz
and J. Vygen, eds., Research Trends in Combinatorial Optimization, Springer, Berlin,
2009, Chapter 11, 219–260.
[241] K. Murota: Submodular function minimization and maximization in discrete convex
analysis, RIMS Kokyuroku Bessatsu, B23 (2010), 193–211.
[242] K. Murota and K. Tanaka: A steepest descent algorithm for M-convex functions on
jump systems, IEICE Transactions on Fundamentals of Electronics, Communications
and Computer Sciences, E89-A (2006), 1160–1165.
[243] A. Shioura: On the pipage rounding algorithm for submodular function maximization: A view from discrete convex analysis, Discrete Mathematics, Algorithms andApplications, 1 (2009), 1–23.
[244] A. Shioura and K. Tanaka: Polynomial-time algorithms for linear and convex optimization on jump systems, SIAM Journal on Discrete Mathematics, 21 (2007),
504–522.
[245] A. Tamura: Applications of discrete convex analysis to mathematical economics,
Publications of Research Institute for Mathematical Sciences, 40 (2004), 1015–1037.
[246] P. Zipkin: On the structure of lost-sales inventory models, Operations Research, 56(2008), 937–944.
(end)

7