TR-2019-07

Discrete Decreasing Minimization, Part I: Base-polyhedra with Applications in Network Optimization

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 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:

@techreport{egres-19-07,
AUTHOR = {Frank, Andr{\'a}s and Murota, Kazuo},
TITLE = {Discrete Decreasing Minimization, Part I: Base-polyhedra with Applications in Network Optimization},
NOTE= {{\tt www.cs.elte.hu/egres}},
INSTITUTION = {Egerv{\'a}ry Research Group, Budapest},
YEAR = {2019},
NUMBER = {TR-2019-07}
}


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