  This paper is concerned with algorithms and applications of decreasing
minimization on an M-convex set, which is the set of integral elements of an
integral base-polyhedron. Based on a recent characterization of decreasingly
minimal (dec-min) elements, we develop a strongly polynomial algorithm for
computing a dec-min element of an M-convex set. The matroidal feature of the
set of dec-min elements makes it possible to compute a minimum cost dec-min
element, as well. Our second goal is to exhibit various applications in matroid
and network optimization, resource allocation, and (hyper)graph orientation. We
extend earlier results on semi-matchings to a large degree by developing a
structural description of dec-min in-degree bounded orientations of a graph.
This characterization gives rise to a strongly polynomial algorithm for finding
a minimum edge-cost dec-min orientation.
