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

András Frank, Kazuo Murota

Published 2018-08-25Version 1

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 are derived as special cases of the Fenchel-type duality in DCA. 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.