TR-2019-08

Discrete Decreasing Minimization, Part II: Views from Discrete Convex Analysis

András Frank, Kazuo Murota



Abstract

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:

@techreport{egres-19-08,
AUTHOR = {Frank, Andr{\'a}s and Murota, Kazuo},
TITLE = {Discrete Decreasing Minimization, Part II: Views from Discrete Convex Analysis},
NOTE= {{\tt www.cs.elte.hu/egres}},
INSTITUTION = {Egerv{\'a}ry Research Group, Budapest},
YEAR = {2019},
NUMBER = {TR-2019-08}
}


Last modification: 29.12.2020. Please email your comments to Tamás Király!