|
We continue to consider the discrete decreasing minimization problem on
an integral base-polyhedron treated in Part~I.
The problem is to find a lexicographically minimal integral vector
in an integral base-polyhedron,
where the components of a vector are arranged in a decreasing order.
This study can be regarded as a discrete counter-part of the work by Fujishige (1980)
on the lexicographically optimal base
and the principal partition of a base-polyhedron in continuous variables.
The objective of Part II is two-fold.
The first is to offer structural views from discrete convex analysis (DCA)
on the results of Part~I obtained by the constructive and algorithmic approach.
The second objective is to pave the way of DCA approach to
discrete decreasing minimization on other discrete structures
(the intersection of M-convex sets, flows, submodular flows)
that we consider in Parts III and IV.
We derive the structural results in Part~I
from fundamental facts on M-convex sets and M-convex functions in DCA.
The characterization of decreasing minimality
in terms of 1-tightening steps (exchange operations)
is derived from the local condition of global minimality
for M-convex functions, known as M-optimality criterion in DCA.
The min-max formulas,
including the one for the square-sum of components,
are derived as special cases of the Fenchel-type discrete duality in DCA.
A general result on the Fenchel-type discrete duality in DCA
offers a short alternative proof to the statement that
the decreasingly minimal elements of an M-convex set form a matroidal M-convex set.
A direct characterization is given to the canonical partition,
which was constructed by an iterative procedure in Part~I.
This reveals the precise relationship
between the canonical partition for the discrete case
and the principal partition for the continuous case.
Moreover, this result entails a proximity theorem,
stating that every decreasingly minimal element
is contained in the small box containing
the (unique) fractional decreasingly minimal element
(the minimum-norm point),
leading further to a continuous relaxation algorithm
for finding a decreasingly minimal element of an M-convex set.
Thus the relationship between the continuous and discrete cases is completely clarified.
Furthermore, we present DCA min-max formulas
to be needed in Parts III and IV,
where the discrete decreasing minimization problem is considered
for network flows, the intersection of two M-convex sets, and submodular flows.
Bibtex entry:
| AUTHOR | = | {Frank, Andr{\'a}s and Murota, Kazuo}, |
| TITLE | = | {Discrete Decreasing Minimization, Part II: Views from Discrete Convex Analysis}, |
| NOTE | = | {{\tt egres.elte.hu}}, |
| INSTITUTION | = | {Egerv{\'a}ry Research Group, Budapest}, |
| YEAR | = | {2019}, |
| NUMBER | = | {TR-2019-08} |