{
  "id": "2007.09618",
  "version": "v1",
  "published": "2020-07-19T08:18:26.000Z",
  "updated": "2020-07-19T08:18:26.000Z",
  "title": "Decreasing Minimization on M-convex Sets: Algorithms and Applications",
  "authors": [
    "András Frank",
    "Kazuo Murota"
  ],
  "comment": "30 pages. This is a revised version of the second half of \"A. Frank and K. Murota; Discrete decreasing minimization, PartI: Base-polyhedra with applications in network optimization\" arXiv:1808.07600",
  "categories": [
    "math.CO"
  ],
  "abstract": "This paper is concerned with algorithms and applications of decreasing minimization on an M-convex set, which is the set of integral elements of an integral base-polyhedron. Based on a recent characterization of decreasingly minimal (dec-min) elements, we develop a strongly polynomial algorithm for computing a dec-min element of an M-convex set. The matroidal feature of the set of dec-min elements makes it possible to compute a minimum cost dec-min element, as well. Our second goal is to exhibit various applications in matroid and network optimization, resource allocation, and (hyper)graph orientation. We extend earlier results on semi-matchings to a large degree by developing a structural description of dec-min in-degree bounded orientations of a graph. This characterization gives rise to a strongly polynomial algorithm for finding a minimum cost dec-min orientation.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2020-07-19T08:18:26.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "90C27",
      "68R10"
    ],
    "keywords": [
      "m-convex set",
      "decreasing minimization",
      "applications",
      "strongly polynomial algorithm",
      "minimum cost dec-min orientation"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 30,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}