数理解析研究所講究録 1297 巻 2002 年 1-11

1Proximity Theorems of Discrete Convex Functions
東京大学・情報理工学研究科

室田一雄 (Kazuo Murota)

Graduate School of Information Science and Technology, University of Tokyo
京都大学・数理解析研究所

田村明久 (Akihisa Tamura)Research Institute for Mathematical Sciences, Kyoto University
Abstract

Aproximity theorem is astatement that, given an optimization problem and its
relaxation, an optimal solution to the original problem exists in acertain neighborhood of asolution to the relaxation. Proximity theorems have been used successfully,
for example, in designing efficient algorithms for discrete resource allocation problems. After reviewing the recent results for -convex and -convex functions, thispaper establishes proximity theorems for larger classes of discrete convex functions,-convex functions and -convex functions, that are relevant to the polymatroidintersection problem and the submodular flow problem.
$\mathrm{M}$$\mathrm{L}$$\mathrm{M}_{2}$$\mathrm{L}_{2}$1Introduction
In the area of discrete optimization, nonlinear optimization problems have been investigated as well as linear optimization problems. Submodular (set) functions and separable
convex functions are well-known examples of tractable nonlinear functions, in that the submodular function minimization problem can be solved in polynomial time (see [13, 14, 24]),and separable convex functions have been treated successfully in many different discrete

optimization problems (see [11]).
Recently, certain classes of “discrete convex functions” were proposed:
convex functions of Murota $[18, 19]$ . -convex functions contain the class of submodular
set functions. -convex functions possess structures of matroids and polymatroids. Separable discrete convex functions can be characterized as functions with both L-convexity
functions con-convex functions andand -convexity(in their variants).
stitute larger classes of discrete convex functions that are relevant to the polymatroidintersection problem, where an -convex function is, by definition, the infimal convolu-convex function is the sum of two M-convex
tion of two -convex functions and an-convex function minimization problem is equivalent to the M-convex
functions. The
submodular flow problem [20] which is an extension of the submodular flow problem [3].
Those classes of discrete convex functions possess the following features in com$\{\mathrm{L},\mathrm{M},\mathrm{L}_{2},\mathrm{M}_{2}\}-$$\mathrm{L}$$\mathrm{M}$$\mathrm{M}_{2^{-}}\mathrm{c}\mathrm{o}\mathrm{n}\mathrm{v}\mathrm{e}\mathrm{x}$$\mathrm{M}$$\mathrm{L}_{2}$$\mathrm{L}_{2}$$\mathrm{M}_{2}$$\mathrm{L}$$\mathrm{M}_{2}$

$C$

$f$

2
, i.e., :Discreteness: is defined on an integral latticeand denote the sets of integers and reals, respectively.
$f$

$f$

$\mathrm{Z}^{n}$$\mathrm{Z}^{n}arrow \mathrm{R}\cup\{+\infty\}$, where$\mathrm{Z}$$\mathrm{R}$Convex Extendibility: There exists acontinuous convex function$f(x)$ for all.

$\overline{f}$such that$\overline{f}(x)=$$x\in \mathrm{Z}^{n}$

Optimality Criterion: There exists aneighborhoodthat$Nc(x^{*})\subset \mathrm{Z}^{n}$with center$f(x^{*})\leq f(x)(\forall x\in \mathrm{Z}^{n})\Leftrightarrow f(x^{*})\leq f(x)(\forall x\in N_{C}(x^{*}))$$x^{*}$

such.

Optimality criterion says that global minimality is implied by local minimality defined interms of the neighborhood $Nc(x^{*})$ . This is asignificant feature inherited from continuous
convex functions.
Moreover, L-/M-convex functions have a“proximity property” described as

Proximity Property: Given apositive integer aand apoint
function $dc(n, \alpha)$ such that$f(x^{\alpha}) \leq f(x)(\forall x\in N_{C}^{\alpha}(x^{\alpha}))\Rightarrow\exists x^{*}\in\arg\min f$

where
all minimizers of , i.e.,$N_{C}^{\alpha}(x^{\alpha})=\{x^{\alpha}+\alpha(x-x^{\alpha})|x\in N_{c}(x^{\alpha})\}$:$x^{\alpha}\in \mathrm{Z}^{n}$, there exists a$||x^{*}-x^{\alpha}||_{\infty}\leq dc(n, \alpha)$,

and $\arg\min f$ denotes the set of$f$$\arg\min f=\{x\in \mathrm{Z}^{n}|f(x)\leq f(y)(\forall y\in \mathrm{Z}^{n})\}$The proximity property says that alocally minimal solution$f^{\alpha}(x)=f(x^{\alpha}+\alpha x)$$x^{\alpha}$.

of a“scaled” function$(x\in \mathrm{Z}^{V})$. For L-/M-convex functions, $d_{c}(n, \alpha)=$is close to aminimizer of in terms of$(n-1)(\alpha-1)$ is avalid choice ([15] and [16], respectively). The proximity property canbe exploited in developing an efficient scaling algorithm for minimizing . In fact, the-convex function minimization problem can be solved in polynomial-time by combining
submodular set function minimization algorithms and the proximity property [12] (seealso [21] . For the -convex function minimization, polynomial-time scaling algorithms
based on the proximity property and its generalization are known $[25, 26]$ . Proximity theorems for separable discrete convex functions are found in [8, 9, 17] in developing efficientalgorithms for resource allocation problems. Different types of theorems on proximity
have also been investigated: proximity between integral and real optimal solutions in[1, 2, 7, 9, 10] and proximity for anumber of resource allocation problems with min-max
tyPe objective functions in [5].
-convex functions. Our main
This paper addresses proximity properties ofresults say:$x^{*}$$f$$d_{c}(n, \alpha)$$f$$\mathrm{L}$$)$$\mathrm{M}$$\mathrm{L}_{2^{-}}/\mathrm{M}_{2}$3for an essentially boundedsatisfies$\bullet$$\mathrm{L}_{2^{-}}\mathrm{c}\mathrm{o}\mathrm{n}\mathrm{v}\mathrm{e}\mathrm{x}$function$f$and apositive integer$\alpha$, if$x^{\alpha}\in$$\mathrm{d}\mathrm{o}\mathrm{m}f$$f(x^{\alpha})\leq f(x^{\alpha}+\alpha\chi_{S})$for all$S\subseteq V$, then there exists $x^{*} \in\arg\min f$ such that,$||x^{*}-x^{\alpha}||_{\infty}\leq 2(n-1)(\alpha-1)$$\bullet$

function represented as the sum of two
for ansatisfies
and , and apositive integer , if$\mathrm{M}_{2^{-}}\mathrm{c}\mathrm{o}\mathrm{n}\mathrm{v}\mathrm{e}\mathrm{x}$$f_{2}$$f$$\mathrm{M}$-convex functions$f1$$x^{\alpha}\in \mathrm{d}\mathrm{o}\mathrm{m}f$$\alpha$$\sum_{i=1}^{k}(f_{1}(x^{\alpha}-\alpha\chi_{u}.+\alpha\chi_{w}.\cdot)-f_{1}(x^{\alpha}))+\sum_{i=1}^{k}(f_{2}(x^{\alpha}-\alpha\chi_{u_{i+1}}+\alpha\chi_{w:})-f_{2}(x^{\alpha}))\geq 0$

for any ordered sets $U=\{u_{1}, \ldots, u_{k}\}$ , $W=\{w_{1}, \ldots, w_{k}\}\subset V$ with $U\cap W=\emptyset$ where$u_{k+1}=u_{1}$ , then there exists $x^{*} \in\arg\min f$ such that$||x^{*}-x^{\alpha}||_{\infty} \leq\frac{n^{2}}{2}(\alpha-1)$.

Section 2states definitions, optimality criteria and proximity properties for several classesof discrete convex functions.

2Definitions, Optimality Criteria and Proximity Theorems, ,In this section, we introduce four classes of discrete convex functions, namely,,-convex functions with respect to definitions, optimality criteria and proximity-convex functions due to [6]theorems. While other variants of these classes, e.g.,-convex functions due to [22], are known, we concentrate on the above fourandclasses because the results can be easily extended to the variants.
Subsections 2.3 and 2.4 present new results, an optimality criterion (Theorem 2.8)
and aproximity property (Theorem 2.9) for -convex functions, and proximity proper-convex functions. Subsection 2.2 also gives anew
ties (Theorems 2.12 and 2.13) for
proximity property (Theorem 2.6) for -convex functions in terms of .-norm. Subsections 2.1 and 2.2 explain known results, optimality criteria and proximity theorems for-convexity and -convexity, respectively. Subsection 2.4 introduce optimality criteria-convexity, which are direct consequences of results for the -convex submodular
for$\{\mathrm{L}$$\mathrm{L}_{2}$$\mathrm{M}$$\mathrm{M}_{2}\}$$\mathrm{L}\#-/\mathrm{L}_{2}^{\#}$$\mathrm{M}\#-/\mathrm{M}_{2}^{\#}$$\mathrm{L}_{2}$$\mathrm{M}_{2}$$\ell_{1}$$\mathrm{M}$$\mathrm{M}$$\mathrm{L}$$\mathrm{M}$$\mathrm{M}_{2}$flow problem.
be anonempty finite set and put $n=|V|$ . We
We first introduce notations. Let
the set of all integral vectors $x=$ $(x(v) : v\in V)$ indexed by , and bydenote by, the effective
the set of all positive integers. Given afunction :domain of is defined by
$V$

$V$

$\mathrm{Z}^{V}$$f$$\mathrm{Z}_{++}$$\mathrm{Z}^{V}arrow \mathrm{R}\cup\{\pm\infty\}$$f$$\mathrm{d}\mathrm{o}\mathrm{m}f=\{x\in \mathrm{Z}^{V}|f(x)\neq\pm\infty\}$.

4For each$S\subseteq V$, we denote by

the characteristic vector of$\chi s$10$\chi_{S}(v)=\{$$S$

defined by$(v\in S)$$(v\in V)$$(v\not\in S)$

for each $u\in V$ . We also denote by 0and 1the vectors
instead ofand write simply
with $x\leq y$ ,denotesof all zeros and ones, respectively. For two vectors ,the set $\{z\in \mathrm{Z}^{V}|x\leq z\leq y\}$ .
$\chi\{u\}$$\chi_{u}$

$x$

2.1

$\mathrm{L}$$x$$y\in \mathrm{Z}^{V}$, the vectors$x\wedge y$and $x\vee y$ in$(x \wedge y)(v)=\min\{x(v), y(v)\}$ ,Afunction :following two conditions:$\mathrm{Z}^{V}arrow \mathrm{R}\cup\{+\infty\}$$f$$\mathrm{Z}^{V}$

are such that$(x \vee y)(v)=\max\{x(v), y(v)\}$is said to be$L$-convex if$\mathrm{d}\mathrm{o}\mathrm{m}f\neq\emptyset$$(v\in V)$.

and it satisfies theis submodular, i.e.,$f$$f(x)+f(y)\geq f(x\wedge y)+f(x\vee y)$(TRF)$[x, y]\mathrm{z}$-convex Functions

For any ,(SBF)$y\in \mathrm{Z}^{V}$$\exists r\in \mathrm{R}$such that $f(x+1)=f(x)+r$$(\forall x\in \mathrm{Z}^{V})$$(\forall x, y\in \mathrm{Z}^{V})$,.

Global optimality of an -convex function is characterized by local optimality.
$\mathrm{L}$Theorem 2.1 ( -optimality criterion, [21])For an -convex function :$\mathrm{L}$

$L$

$f$

$\mathrm{Z}^{V}arrow \mathrm{R}\cup\{+\infty\}$and$x^{*}\in \mathrm{d}\mathrm{o}\mathrm{m}f$$f(x^{*})\leq f(x^{*}+\chi_{S})$$f(x^{*})\leq f(x)$$(\forall x\in \mathrm{Z}^{V})$$\Leftrightarrow$$\{$$f(x^{*}+1)=f(x^{*})$, we have$(\forall S\subseteq V)$,.

The above local optimality criterion can be checked in polynomial time because the first
condition can be verified by using submodular function minimization algorithms and thesecond condition is easy.
We next introduce aproximity theorem of -convex functions.
$\mathrm{L}$Theorem 2.2 ( -proximity theorem, [15])be an -convex function with $f(x+1)=f(x)(\forall x\in \mathrm{Z}^{V})$
Let :
. If
and letsatisfies$\mathrm{L}$$f$$\mathrm{Z}^{V}arrow \mathrm{R}\cup\{+\infty\}$$\alpha\in \mathrm{Z}_{++}$$L$$x^{\alpha}\in \mathrm{d}\mathrm{o}\mathrm{m}f$$f(x^{\alpha})\leq f(x^{\alpha}+\alpha\chi_{S})$then $\arg$ $\min$$f\neq\emptyset$$(\forall S\subseteq V)$,

and ttere exists $x^{*} \in\arg\min f$ with$x^{\alpha}\leq x^{*}\leq x^{\alpha}+(n-1)(\alpha-1)1$.

Remark 2.3 Theorems 2.1 and 2.2 are extended to amore general class of “quasi” Lconvex functions [23]5
2.2$\mathrm{M}$-convex Functions

We define the positive support and negative support of a vector $x=$ $(x(v) : v\in V)\in \mathrm{Z}^{V}$by.
and$\mathrm{s}\mathrm{u}\mathrm{p}\mathrm{p}^{-}(x)=\{v\in V|x(v)<0\}$$\mathrm{s}\mathrm{u}\mathrm{p}\mathrm{p}^{+}(x)=\{v\in V|x(v)>0\}$

Afunction$f$:$\mathrm{Z}^{V}arrow \mathrm{R}\cup\{+\infty\}$( -EXC)for ,$x$$\mathrm{M}$$y\in \mathrm{d}\mathrm{o}\mathrm{m}f$andis called $M$-convex if$u\in \mathrm{s}\mathrm{u}\mathrm{p}\mathrm{p}^{+}(x-y)$$\mathrm{d}\mathrm{o}\mathrm{m}f\neq\emptyset$, there exists

and it satisfies$v\in \mathrm{s}\mathrm{u}\mathrm{p}\mathrm{p}^{-}(x-y)$$f(x)+f(y)\geq f(x-\chi_{u}+\chi_{v})+f(y+\chi_{u}-\chi_{v})$

We note that ( -EXC)is also represented as: for ,$x$$\mathrm{M}$$y\in \mathrm{d}\mathrm{o}\mathrm{m}f$such that.

,$f(x)+f(y) \geq\max_{u\in\sup \mathrm{p}^{+}}\min_{(x-y)v\in\sup \mathrm{p}^{-}(x-y)}[f(x-\chi_{u}+\chi_{v})+f(y+\chi_{u}-\chi_{v})]$,, respectively.
where the maximum and the minimum over an empty set
lies on ahyperplane $\{x\in \mathrm{R}^{V}|x(V)=$Prom ( -EXC), the effective domain
is the set of integer
constant}, where $x(V)= \sum_{v\in V}x(v)$ . It is also known thatpoints of the base polyhedron of an integral submodular system (see [4] for submodular$\mathrm{a}\mathrm{r}\mathrm{e}-\infty \mathrm{a}\mathrm{n}\mathrm{d}+\infty$$\mathrm{M}$$\mathrm{d}\mathrm{o}\mathrm{m}f$$\mathrm{d}\mathrm{o}\mathrm{m}f$systems).

The minimizers of anchecked efficiently.

$\mathrm{M}$-convex function have anice characterization which can be

Theorem 2.4 ( -optimality criterion, [18, 19])and
For an $M$-convex function :$\mathrm{M}$$f$$f(x^{*})\leq f(x)(\forall x\in \mathrm{Z}^{V})$$\mathrm{Z}^{V}arrow \mathrm{R}\cup\{+\infty\}$$\Leftrightarrow$$f(x^{*})\leq f(x^{*}-\chi_{u}+\chi_{v})$We next introduce aproximity theorem ofTheorem 2.5 (Let f :$\mathrm{M}$$x^{*}\in \mathrm{d}\mathrm{o}\mathrm{m}f$$\mathrm{M}$, we have(Vtt, $v\in V$ ).

-convex functions.

-proximity theorem, [16])be an $M$-convex function and let$\mathrm{Z}^{V}arrow \mathrm{R}\cup\{+\infty\}$satisfies$f(x^{\alpha})\leq f(x^{\alpha}-\alpha\chi_{u}+\alpha\chi_{v})$(Vu, v$\alpha\in \mathrm{z}_{++}$$\subseteq V$. If$x^{\alpha}\in \mathrm{d}\mathrm{o}\mathrm{m}f$),then $\arg\min f\neq\emptyset$ and there exists $x^{*} \in\arg\min f$ with$|x^{\alpha}(v)-x^{*}(v)|\leq(n-1)(\alpha-1)$$(\forall v\in V)$.

By slightly modifying the proof of [16], we also obtain the following proximity theorem interms of -norm.
$\ell_{1}$6
Theorem 2.6$x^{\alpha}\in \mathrm{d}\mathrm{o}\mathrm{m}$Let f :

be an $M$-convex function and let$\mathrm{Z}^{V}arrow \mathrm{R}\cup\{+\infty\}$$\alpha\in \mathrm{Z}_{++}$. If

f satisfies$f(x^{\alpha})\leq f(x^{\alpha}-\alpha\chi_{u}+\alpha\chi_{v})$$(\forall u, v\subseteq V)$,(1)then $\arg\min f\neq\emptyset$ and there exists $x^{*} \in\arg\min f$ with$||x^{*}-x^{\alpha}||_{1} \leq\frac{n^{2}}{2}(\alpha-1)$.

(2)

Remark 2.7 Theorems 2.4 and 2.5 are extended to amore general class of “quasi” Mconvex functions [23].

2.3$\mathrm{L}_{2}$-convex Functions

For any functions $f1$ ,by:$f_{1}\square f_{2}$$f_{2}$:$\mathrm{Z}^{V}arrow \mathrm{R}\cup\{+\infty\}$$\mathrm{Z}^{V}arrow \mathrm{R}\cup\{\pm\infty\}$, the infimal convolution of$f_{1}$

and$f_{2}$, denoted, is defined by$(f_{1} \square f_{2})(x)=\inf\{f_{1}(x_{1})+f_{2}(x_{2})|x_{1}+x_{2}=x, x_{1}, x_{2}\in \mathrm{Z}^{V}\}$

It is easy to show that if $f1\square f_{2}>-\infty$ then the effective domain of
the Minkowski sum of the effective domains of and , that is,$f_{1}$$(x\in \mathrm{Z}^{V})$$fi\square f_{2}$.

coincides with$f_{2}$.

$\mathrm{d}\mathrm{o}\mathrm{m}(f_{1}\square f_{2})=(\mathrm{d}\mathrm{o}\mathrm{m}f_{1})+(\mathrm{d}\mathrm{o}\mathrm{m}f_{2})\equiv\{x_{1}+x_{2}|x_{1}\in \mathrm{d}\mathrm{o}\mathrm{m}f_{1}, x_{2}\in \mathrm{d}\mathrm{o}\mathrm{m}f_{2}\}$

It is known that the infimal convolution of two -convex functions is also -convex, but
the infimal convolution of two -convex functions may not be -convex[18]. Afunction:
is said to be -convex if
and $f=f1\square f_{2}$ for some
. We say that an-convex functions , :-convex function
is essentially bounded if
is bounded for some $v\in V$ . If an
are also essentiallyfunction $f=f1\square f_{2}$ is essentially bounded, thenandbounded, because
holds forfunction .
functions
The following optimality criterion and the proximity theorem forare new results. We emphasize that the optimality criterion is the same as that for Lconvex functions stated in Theorem 2.1 and that the proximity theorem is almost thesame as that stated in Theorem 2.2.
$\mathrm{M}$$\mathrm{M}$$\mathrm{L}$$f$$\mathrm{L}$$\mathrm{Z}^{V}arrow \mathrm{R}\cup\{+\infty\}$$\mathrm{L}$$f_{1}$$L_{2}$$f_{2}$$\mathrm{d}\mathrm{o}\mathrm{m}f\neq\emptyset$$\mathrm{Z}^{V}arrow \mathrm{R}\cup\{+\infty\}$$f$$\mathrm{L}-/\mathrm{L}_{2}$$\mathrm{d}\mathrm{o}\mathrm{m}f\cap\{x\in \mathrm{Z}^{V}|x(v)=0\}$$f_{1}$$\mathrm{L}_{2^{-}}\mathrm{c}\mathrm{o}\mathrm{n}\mathrm{v}\mathrm{e}\mathrm{x}$$\mathrm{d}\mathrm{o}\mathrm{m}f=(\mathrm{d}\mathrm{o}\mathrm{m}f1)+(\mathrm{d}\mathrm{o}\mathrm{m}f_{2})$$f_{2}$$f$$\mathrm{L}_{2^{-}}\mathrm{c}\mathrm{o}\mathrm{n}\mathrm{v}\mathrm{e}\mathrm{x}$$\mathrm{L}_{2^{-}}\mathrm{c}\mathrm{o}\mathrm{n}\mathrm{v}\mathrm{e}\mathrm{x}$Theorem 2.8 ( -optimality criterion)
For an -convex function :$\mathrm{L}_{2}$$L_{2}$$f$$\mathrm{Z}^{V}arrow \mathrm{R}\cup\{+\infty\}$and$x^{*}\in \mathrm{d}\mathrm{o}\mathrm{m}f$$f(x^{*})\leq f(x^{*}+\chi s)$$f(x^{*})\leq f(x)$$(\forall x\in \mathrm{Z}^{V})$$\Leftrightarrow$$\{$$f(x^{*}+1)=f(x^{*})$.

, we have$(\forall S\subseteq V)$,

7
Theorem 2.9 (Let f :

-proximity theorem)
be an essentially bounded -convex function with $f(x+1)=$. If
and letf satisfies$\mathrm{L}_{2}$$L_{2}$$\mathrm{Z}^{V}arrow \mathrm{R}\cup\{+\infty\}$$f(x)(\forall x\in \mathrm{Z}^{V})$$x^{\alpha}\in \mathrm{d}\mathrm{o}\mathrm{m}$$\alpha\in \mathrm{Z}_{++}$$f(x^{\alpha})\leq f(x^{\alpha}+\alpha\chi_{S})$$(\forall S\subseteq V)$,then $\arg\min f\neq\emptyset$ and there exists $x^{*} \in\arg\min f$ with$x^{\alpha}\leq x^{*}\leq x^{\alpha}+2(n-1)(\alpha-1)1$

2.4$\mathrm{M}_{2}$.

-convex Functions

It is known that the sum of two -convex functions is not necessarily -convex. Afuncand $f=f1+f_{2}$ for-convex if
is said to betion :. It is easy to show thatsome -convex functions , :and is identically zero, then $f=f_{1}$. Obviously, if
is -convex, and hence, the class of -convex functions includes that of -convex func-convex function minimization problem contains the polymatroid intertions. The-convexity below are
section problem as aspecial case. Thus, optimality criteria forextensions of known results for the matroid intersection problem and the polymatroidintersection problem.
and $f[p](x)$ by, let us define functions
For avector$\mathrm{M}$$\mathrm{M}$$\mathrm{Z}^{V}arrow \mathrm{R}\cup\{+\infty\}$$f$$\mathrm{M}$$\mathrm{d}\mathrm{o}\mathrm{m}f\neq\emptyset$$M_{2}$$f_{1}$$f_{2}$$\mathrm{d}\mathrm{o}\mathrm{m}f_{1}=\mathrm{d}\mathrm{o}\mathrm{m}f_{2}$$(\mathrm{d}\mathrm{o}\mathrm{m}f_{1})\cap(\mathrm{d}\mathrm{o}\mathrm{m}f_{2})$$\mathrm{d}\mathrm{o}\mathrm{m}f=$$\mathrm{Z}^{V}arrow \mathrm{R}\cup\{+\infty\}$$f_{2}$$\mathrm{M}$$\mathrm{M}$$\mathrm{M}_{2}$$\mathrm{M}_{2}$$\mathrm{M}_{2}$$p\in \mathrm{R}^{V}$$\langle p, x\rangle$

and$\langle p, x\rangle=\sum_{v\in V}p(v)x(v)$If$f[p](x)=f(x)+\langle p, x\rangle$$(x\in \mathrm{Z}^{V})$.

is -convex, then $f[p]$ is also M-convex.
Several results on optimality of -convexity are known.

$f$$\mathrm{M}$$\mathrm{M}_{2}$Theorem 2.10 ( -convex intersection theorem, [18])and a point
For $M$-convex functions , :we have$\mathrm{M}$$f1$$f_{2}$$\mathrm{Z}^{V}arrow \mathrm{R}\cup\{+\infty\}$$f_{1}(x^{*})+f_{2}(x^{*})\leq f_{1}(x)+f_{2}(x)$if and only if there exists$p^{*}\in \mathrm{R}^{V}$$x^{*}\in \mathrm{d}\mathrm{o}\mathrm{m}f_{1}\cap \mathrm{d}\mathrm{o}\mathrm{m}f_{2\prime}$$(\forall x\in \mathrm{Z}^{V})$such that$f_{1}[-p^{*}](x^{*})$$\leq$$f_{1}[-p^{*}](x)$$(\forall x\in \mathrm{Z}^{V})$,$f_{2}[+p^{*}](x^{*})$$\leq$$f_{1}[+p^{*}](x)$$(\forall x\in \mathrm{Z}^{V})$,and furthermore, we have$\arg\min(f1+f_{2})=\arg\min(f1[-p^{*}])\cap\arg\min(f_{2}[+p^{*}])$

for such$p^{*}$.

8
Optimality criteria offunctions can be transformed from those of the Mconvex submodular flow problem in [19], because thefunction minimizationand the -convex submodular flow problem are equivalent to each other. The following
theorem is adirect consequence of the results in [19].
$\mathrm{M}_{2^{-}}\mathrm{c}\mathrm{o}\mathrm{n}\mathrm{v}\mathrm{e}\mathrm{x}$$\mathrm{M}_{2^{-}}\mathrm{c}\mathrm{o}\mathrm{n}\mathrm{v}\mathrm{e}\mathrm{x}$$\mathrm{M}$criteria, see [19])Theorem 2.11 (and a point
For $M$-convex functions $fi$ , :three conditions below are equivalent:$\mathrm{M}_{2^{-}}\mathrm{o}\mathrm{p}\mathrm{t}\mathrm{i}\mathrm{m}\mathrm{a}1\mathrm{i}\mathrm{t}\mathrm{y}$$\mathrm{Z}^{V}arrow \mathrm{R}\cup\{+\infty\}$$f_{2}$(a)$x^{*} \in\arg\min(f1+f_{2})$$x^{*}\in \mathrm{d}\mathrm{o}\mathrm{m}f1\cap \mathrm{d}\mathrm{o}\mathrm{m}f_{2}$,.

(b) For any ordered sets $U=\{u_{1}, \ldots, u_{k}\}$ , $W=\{w_{1}, \ldots, w_{k}\}\subset V$ with $U\cap W=\emptyset$ ,$\sum_{\dot{\iota}=1}^{k}(f_{1}(x^{*}-\chi_{u}:+\chi_{w:})-f_{1}(x^{*}))+\sum_{i=1}^{k}(f_{2}(x^{*}-\chi_{u}:+1+\chi_{w}\dot{.})-f_{2}(x^{*}))\geq 0$,

where $u_{k+1}=u_{1}$ .
(c)$(\forall U, W\subset V, |U|=|W|)$$(f_{1}+f_{2})(x^{*})\leq(f1+f_{2})(x^{*}-\chi u+\chi w)$.

can be checked in polynomial time by transforming
The optimality for(b) of Theorem 2.11 to anetwork problem (see Remark 2.14), although checking condition(c) of Theorem 2.11 seems to be ahard problem. In view of polynomial time verifiability,
functions.
we relax (b) of Theorem 2.11 to formulate aproximity theorem ofThis is the main result of this paper.
$\mathrm{M}_{2^{-}}\mathrm{c}\mathrm{o}\mathrm{n}\mathrm{v}\mathrm{e}\mathrm{x}\mathrm{i}\mathrm{t}\mathrm{y}$$\mathrm{M}_{2^{-}}\mathrm{c}\mathrm{o}\mathrm{n}\mathrm{v}\mathrm{e}\mathrm{x}$Theorem 2.12 (:Let ,$f_{1}$$f_{2}$$\mathrm{M}_{2^{-}}\mathrm{p}\mathrm{r}\mathrm{o}\mathrm{x}\mathrm{i}\mathrm{m}\mathrm{i}\mathrm{t}\mathrm{y}$theorem)
be $M$-convex functions and let$\mathrm{Z}^{V}arrow \mathrm{R}\cup\{+\infty\}$$\mathrm{d}\mathrm{o}\mathrm{m}f_{1}\cap \mathrm{d}\mathrm{o}\mathrm{m}f_{2}$$\alpha\in \mathrm{Z}_{++}$.

If$x^{\alpha}\in$satisfies$\sum_{\dot{l}=1}^{k}(f_{1}(x^{\alpha}-\alpha\chi_{u}:+\alpha\chi_{w}.\cdot)-f_{1}(x^{\alpha}))+\sum_{i=1}^{k}(f_{2}(x^{\alpha}-\alpha\chi_{u}:+1+\alpha\chi_{w}:)-f_{2}(x^{\alpha}))\geq 0$, $W=\{w_{1}, \ldots, w_{k}\}\subset V$ with $U\cap W=\emptyset$ where $u_{k+1}=$, then $\arg\min(f_{1}+f_{2})\neq\emptyset$ and there exists $x^{*} \in\arg\min(f_{1}+f_{2})$ withfor any ordered sets$u_{1}$$U=\{u_{1}, \ldots, u_{k}\}$$||x^{*}-x^{\alpha}||_{\infty} \leq\frac{n^{2}}{2}(\alpha-1)$.

(3)

The proof of Theorem 2.12 relies heavily on the following result.
be $M$-convex functions with $\arg\min(f1+$
Let , :
Theorem 2.13
, andwith $x(V)=y(V)$ for any. For a given point, if there exist $x^{1} \in\arg\min f_{1}$ and $x^{2} \in\arg\min f_{2}$ such that
for
$f1$

$f_{2})\neq\emptyset$$f_{2}$$\mathrm{Z}^{V}arrow \mathrm{R}\cup\{+\infty\}$$x\in \mathrm{Z}^{V}$$y\in \mathrm{d}\mathrm{o}\mathrm{m}f1\cap \mathrm{d}\mathrm{o}\mathrm{m}f_{2}$$d\in \mathrm{Z}$$||x^{1}-x||_{1}\leq d$,$||x^{2}-x||_{1}\leq d$then there exists $x^{*} \in\arg\min(f1+f_{2})$ with$||x^{*}-x||_{\infty}\leq d$

.

,

(4)

9
Remark 2.14 Condition (b) of Theorem 2.11 can be checked in polynomial time. Givenand, a point:
two -convex functions ,and an arc, we construct adirected graphpositive integer
be copies of , i.e.,
as follows. Let V4 andlength$f1$$\mathrm{M}$$f_{2}$$x\in \mathrm{d}\mathrm{o}\mathrm{m}f_{1}\cap \mathrm{d}\mathrm{o}\mathrm{m}f_{2}$$\mathrm{Z}^{V}arrow \mathrm{R}\cup\{+\infty\}$$G_{x}^{\alpha}=$$\alpha\in \mathrm{Z}_{++}$$V_{1}=\{v_{1}|v\in V\}$where$v_{1}$

andWe define$v_{2}$$(V_{1}\cup \mathrm{I}4, A)$$V$$V_{2}$$\ell_{x}^{\alpha}\in \mathrm{R}^{A}$,$V_{2}=\{v_{2}|v\in V\}$are the copies of $v\in V$ . Arc set$A$,consists of three disjoint parts:,$A_{b}$$=$$\{(v_{1}, v_{2})|v\in V\}\cup\{(v_{2}, v_{1})|v\in V\}$

$A_{1}$$=$$\{(u_{1}, v_{1})|u, v\in V, u\neq v, x-\alpha\chi_{u}+\alpha\chi_{v}\in \mathrm{d}\mathrm{o}\mathrm{m}f1\}$,$A_{2}$$=$$\{(v_{2}, u_{2})|u, v\in V, u\neq v, x-\alpha\chi_{u}+\alpha\chi_{v}\in \mathrm{d}\mathrm{o}\mathrm{m}f_{2}\}$.

$\ell_{x}^{\alpha}\in \mathrm{R}^{A}$$\mathrm{a}$

(5)

by

0
$\ell_{x}^{\alpha}(a)=\{$$(a\in A_{b})$$f_{1}(x-\alpha\chi_{u}+\alpha\chi_{v})-f_{1}(x)$$(a=(u_{1}, v_{1})\in A_{1})$$f_{2}(x-\alpha\chi_{u}+\alpha\chi_{v})-f_{2}(x)$$(a=(v_{2}, u_{2})\in A_{2})$(6).

Lemma 2.15 below guarantees that (b) of Theorem 2.11 can be checked in polynomial
time by aPPlying shortest path algorithms.
Lemma 2.15$\mathrm{d}\mathrm{o}\mathrm{m}f_{1}\cap \mathrm{d}\mathrm{o}\mathrm{m}f_{2}$(a):For trno $M$-convex functions ,, two conditions below are equivalent:
and
$f1$

$f_{2}$$\mathrm{Z}^{V}arrow \mathrm{R}\cup\{+\infty\}$, a point $x\in$$\alpha\in \mathrm{Z}_{++}$

There exists no negative cycle in$G_{x}^{\alpha}$with length$\ell_{x}^{\alpha}$.

(b) For any ordered sets $U=\{u_{1}, \ldots, u_{k}\}$ , $W=\{w_{1}, \ldots, w_{k}\}\subset V$ with $U\cap W=\emptyset$ ,$\sum_{i=1}^{k}(f_{1}(x-\alpha\chi_{u}:+\alpha\chi_{w}:)-f_{1}(x))+\sum_{i=1}^{k}(f_{2}(x-\alpha\chi_{u:+1}+\alpha\chi_{w:})-f_{2}(x))\geq 0$,(7)where $u_{k+1}=u_{1}$ .

References[1] R. Baldick, Refined proximity and sensitivity results in linearly constrained convex
separable integer programming, Linear Algebra Appl. 226/228 (1995), 389-407.

[2] W. Cook, A. M. H. Gerards, A. Schrijver and E. Tardos, Sensitivity theorems in
integer linear programming, Math. Program. 34 (1986), 251-264.
[3] J. Edmonds and R. Giles, Amin-max relation for submodular functions on graphs,
Ann. Discrete Math. 1(1977), 185-204

10[4] S. Fujishige, “Submodular Functions and Optimization ,” Annals of Discrete Mathematics 47, North-Holland, Amsterdam, 1991.
[5] S. Fujishige, N. Katoh and T. Ichimori, The fair resource allocation problem with. 13 (1988), 164-173.
submodular constraints, Math. Oper.
${\rm Res}$[6] S. Fujishige and K. Murota, Notes on L-/M-convex functions and the separation
theorems, Math. Program. 88 (2000), 129-146.
[7] F. Granot and J. Skorin-Kapov, Some proximity and sensitivity results in quadratic
integer programming, Math. Program. 47 (1990), 259-268.
[8] D. S. Hochbaum, Lower and upper bounds for the allocation problem and other. 19 (1994), 390-409.
nonlinear optimization problems, Math. Oper.
${\rm Res}$[9] D. S. Hochbaum and J. G. Shanthikumar, Convex separable optimization is not muchharder than linear optimization, J. Assoc. Comput. Mach. 37 (1990), 843-862.

[10] T. Ibaraki and N. Katoh, “Resource Allocation Problems: Algorithmic Approaches ,”The MIT Press, Cambridge, 1988.
[11] T. Ibaraki and N. Katoh, Resource Allocation Problems, in “Handbook of Combinatorial Optimization (Vol. 2),” (D.-Z. Du and P. M. Pardalos, Eds.), pp. 159-260,
Kluwer Academic Publishers, Boston, 1998.

[12] S. Iwata, Oral presentation at Workshop on Matroids, Matching, and Extensions,
University of Waterloo, December, 1999.

[13] S. Iwata, Afully combinatorial algorithm for submodular function minimization, J.
Combin. Theory Ser. B84 (2002), 203-212.
[14] S. Iwata, L. Fleischer and S. Fujishige, Acombinatorial strongly polynomial alg0rithm for minimizing submodular functions, J. Assoc. Comput. Mach. 48 (2001),

761-777.
[15] S. Iwata and M. Shigeno, Conjugate scaling algorithm for Fenchel-type duality indiscrete convex optimization, SIAM J. Optim., to appear.

[16] S. Moriguchi, K. Murota and A. Shioura, Scaling algorithms for -convex function
minimization, IEICE Trans. Fundamentals E85-A (2002), 922-929.
$\mathrm{M}$[17] S. Moriguchi and A. Shioura, On Hochbaum’s scaling algorithm for the general resource allocation problem, Research Report B-377, Tokyo Institute of Technology

11[18] K. Murota, Convexity and Steinitz’s exchange property, Adv. Math. 124 (1996),
272-311.
[19] K. Murota, Discrete convex analysis, Math. Program. 83 (1998), 313-371.

[20] K. Murota, Submodular flow problem with anonseparable cost function, Combinatorica 19 (1999), 87-109.
[21] K. Murota, “Discrete Convex Analysis –An Introduction (in Japanese),” Kyoritsu
Publ. Co. , Tokyo, 2001.
[22] K. Murota and A. Shioura, -convex function on generalized polymatroid, Math.
. 24 (1999), 95-105.
Oper.
$\mathrm{M}$${\rm Res}$[23] K. Murota and A. Shioura, Quasi M convex and -convex functions: Quasi-convexity
in discrete optimization, Discrete Appl. Math, to appear.
$\mathrm{L}$[24] A. Schrijver, Acombinatorial algorithm minimizing submodular functions in strongly
polynomial time, J. Combin. Theory Ser. B80(2000), 346-355.
[25] A. Shioura, Fast scaling algorithms for -convex function minimization with application to the resource allocation problem, Tohoku University, (2002).
$\mathrm{M}$[26] A. Tamura, Coordinatewise domain scaling algorithm for -convex function minimization, in: “Proceedings of the Ninth Conference on Integer Programming andCombinatorial Optimization,” Lecture Notes in Computer Science Vol. 2337 (W. J.
Cook and A. S. Schulz, Eds.) pp. 21-35, Springer-Verlag, Berlin, 2002$\mathrm{M}$