|
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:
| AUTHOR | = | {Frank, Andr{\'a}s and Murota, Kazuo}, |
| TITLE | = | {Decreasing Minimization on M-convex Sets}, |
| NOTE | = | {{\tt egres.elte.hu}}, |
| INSTITUTION | = | {Egerv{\'a}ry Research Group, Budapest}, |
| YEAR | = | {2020}, |
| NUMBER | = | {TR-2020-11} |