TR-2018-13

Discrete Decreasing Minimization, Part I, Base-polyhedra with Applications in Network Optimization (A revised version is available as TR-2019-07)

András Frank, Kazuo Murota



Abstract

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:

@techreport{egres-18-13,
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 www.cs.elte.hu/egres}},
INSTITUTION = {Egerv{\'a}ry Research Group, Budapest},
YEAR = {2018},
NUMBER = {TR-2018-13}
}


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