|
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 for which the in-degree of its last
node is at least two larger than the in-degree of its first node.
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 generalization 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 \lq lexicographically\rq \
optimal (fractional) network flow problem (1974, 1977).
Furthermore, we exhibit a generalization of a result of Levin and Onn
(2016) on \lq shifted\rq \ 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 et 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.
This paper constitutes the first part of a series of our papers on
discrete decreasing minimization.
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.
In Part~III
we describe the structure of decreasingly minimal integral feasible flows and
develop a strongly polynomial algorithm for finding such a dec-min flow.
In Part~IV we consider
the discrete decreasing minimization problem over the
intersection of two base-polyhedra, and also over submodular flows.
Finally, Part~V deals with discrete decreasing minimality
with respect to a weight vector.
Bibtex entry:
| AUTHOR | = | {Frank, Andr{\'a}s and Murota, Kazuo}, |
| TITLE | = | {Discrete Decreasing Minimization, Part I: Base-polyhedra with Applications in Network Optimization}, |
| NOTE | = | {{\tt egres.elte.hu}}, |
| INSTITUTION | = | {Egerv{\'a}ry Research Group, Budapest}, |
| YEAR | = | {2019}, |
| NUMBER | = | {TR-2019-07} |