TR-2020-11

Decreasing Minimization on M-convex Sets

András Frank, Kazuo Murota



Abstract

The present work is the first member of a pair of papers concerning decreasingly-minimal (dec-min) elements of a set of integral vectors, where a vector is dec-min if its largest component is as small as possible, within this, the next largest component is as small as possible, and so on. This notion showed up earlier under various names at resource allocation, network flow, matroid, and graph orientation problems. Its fractional counterpart was also seriously investigated.
 

 
The domain we consider is an M-convex set, that is, the set of integral elements of an integral base-polyhedron. A fundamental difference between the fractional and the discrete case is that a base-polyhedron has always a unique dec-min element, while the set of dec-min elements of an M-convex set admits a rich structure, described here with the help of a `canonical chain'. As a consequence, we prove that this set arises from a matroid by translating the characteristic vectors of its bases with an integral vector.
 

 
By relying on these characterizations, we prove that an element is dec-min if and only if the square-sum of its components is minimum, a property resulting in a new type of min-max theorems. The characterizations also give rise, as shown in the companion paper, to a strongly polynomial algorithm and to a proof of a conjecture on dec-min orientations.


Bibtex entry:

@techreport{egres-20-11,
AUTHOR = {Frank, Andr{\'a}s and Murota, Kazuo},
TITLE = {Decreasing Minimization on M-convex Sets},
NOTE= {{\tt www.cs.elte.hu/egres}},
INSTITUTION = {Egerv{\'a}ry Research Group, Budapest},
YEAR = {2020},
NUMBER = {TR-2020-11}
}


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