{
  "id": "1808.07600",
  "version": "v1",
  "published": "2018-08-23T00:45:48.000Z",
  "updated": "2018-08-23T00:45:48.000Z",
  "title": "Discrete Decreasing Minimization, Part I, Base-polyhedra with Applications in Network Optimization",
  "authors": [
    "András Frank",
    "Kazuo Murota"
  ],
  "comment": "52 pages",
  "categories": [
    "math.CO"
  ],
  "abstract": "Borradaile et al. (2017) investigated orientations of an undirected graph in which the sequence of in-degrees of the nodes is lexicographically minimal, which we call decreasingly minimal (=dec-min). They 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. We also provide a solution to a discrete version of Megiddo's lexicographically optimal (fractional) network flow problem (1974, 1977). 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. We also 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.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2018-08-23T00:45:48.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "90C27",
      "90C10",
      "90C25"
    ],
    "keywords": [
      "discrete decreasing minimization",
      "dec-min element",
      "network optimization",
      "base-polyhedron",
      "m-convex set"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 52,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}