|
Motivated by resource allocation problems, Borradaile
et al. (2017) investigated orientations of an undirected graph in
which the sequence of in-degrees of the nodes, when arranged in a
decreasing order, is lexicographically minimal in the sense that the
largest in-degree is as small as possible, within this, the next
largest in-degree is as small as possible, and so on. They called
such an orientation egalitarian but we prefer to use the term {\it
decreasingly minimal} ($=$dec-min) to avoid confusion with another
egalitarian-felt orientation where the smallest in-degree is as large
as possible, within this, the next smallest in-degree is as large as
possible, and so on. Borradaile et al. proved that an orientation is
dec-min if and only if there is no dipath from $s$ to $t$ with
in-degrees $\varrho (t) \geq \varrho (s)+2$. They conjectured that an
analogous statement holds for strongly connected dec-min orientations,
as well. We prove not only this conjecture but its extension to
$k$-edge-connected orientations, as well, even if additional in-degree
constraints are imposed on the nodes.
Resource allocation was also the motivation behind an earlier
framework by Harvey et al. (2006) who introduced and investigated
semi-matchings of bipartite graphs. As a genaralization of their
results, we characterize degree-constrained subgraphs of a bipartite
graph $G=(S,T;E)$ which have a given number of edges and their
degree-sequence in $S$ is decreasingly minimal. We also provide a
solution to a discrete version of Megiddo's `lexicographically'
optimal (fractional) network flow problem (1974, 1977).
Furthermore, we exhibit a generalization of a result of Levin and Onn
(2016) on `shifted' matroid optimization, and describe a way of
finding a basis of each of $k$ matroids so that the sum of their
incidence vectors is decreasingly minimal.
Our main goal is to integrate these cases into a single framework.
Namely, we characterize dec-min elements of an M-convex set (which is
nothing but the set of integral points of an integral
base-polyhedron), and prove that the set of dec-min elements is a
special M-convex set arising from a matroid base-polyhedron by
translation. The topic of our investigations may be interpreted as a
discrete counter-part of the work by Fujishige (1980) on the (unique)
lexicographically optimal base of a base-polyhedron. On the dual
side, as an extension of a result of Borradaile at al. (2018) on
density decomposition of networks, we exhibit a canonical chain (and
partition) associated with a base-polyhedron. We also show that
dec-min elements of an M-convex set are exactly those which minimize
the square-sum of components, and describe a new min-max formula for
the minimum square-sum.
Our approach gives rise to a strongly polynomial algorithm for
computing a dec-min element, as well as the canonical chain. The
algorithm relies on a submodular function minimizer oracle in the
general case, which can, however, be replaced by more efficient
classic flow- and matroid algorithms in the relevant special cases.
In Part II, we offer a broader structural view from discrete convex
analysis (DCA). In particular, min-max formulas will be derived as
special cases of general DCA results. Furthermore, the relationship
between continuous and discrete problems will also be clarified.
Finally, Part III of the series describes a strongly polynomial
algorithm for the discrete decreasing minimization problem over the
intersection of two base-polyhedra, and also over submodular flows.
Bibtex entry:
| AUTHOR | = | {Frank, Andr{\'a}s and Murota, Kazuo}, |
| TITLE | = | {Discrete Decreasing Minimization, Part I, Base-polyhedra with Applications in Network Optimization (A revised version is available as TR-2019-07)}, |
| NOTE | = | {{\tt egres.elte.hu}}, |
| INSTITUTION | = | {Egerv{\'a}ry Research Group, Budapest}, |
| YEAR | = | {2018}, |
| NUMBER | = | {TR-2018-13} |