|
We consider discrete decreasing minimization problem on
an integral base-polyhedron.
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.
In contrast to the constructive and algorithmic approach in Part I,
Part II offers structural views from discrete convex analysis (DCA)
by making full use of the fundamental results on
M-convex sets and M-convex functions.
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 duality in DCA;
this approach also yields a novel min-max formula that shows a natural link to majorization.
A general result on the Fenchel-type 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 with a tight bound,
which leads 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.
Bibtex entry:
| AUTHOR | = | {Frank, Andr{\'a}s and Murota, Kazuo}, |
| TITLE | = | {Discrete Decreasing Minimization, Part II: Views from Discrete Convex Analysis (A revised version is available as TR-2019-08)}, |
| NOTE | = | {{\tt egres.elte.hu}}, |
| INSTITUTION | = | {Egerv{\'a}ry Research Group, Budapest}, |
| YEAR | = | {2018}, |
| NUMBER | = | {TR-2018-14} |