{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,27]],"date-time":"2026-02-27T05:43:04Z","timestamp":1772170984950,"version":"3.50.1"},"reference-count":56,"publisher":"Springer Science and Business Media LLC","issue":"1-2","license":[{"start":{"date-parts":[[2021,10,15]],"date-time":"2021-10-15T00:00:00Z","timestamp":1634256000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2021,10,15]],"date-time":"2021-10-15T00:00:00Z","timestamp":1634256000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Math. Program."],"published-print":{"date-parts":[[2022,9]]},"DOI":"10.1007\/s10107-021-01711-5","type":"journal-article","created":{"date-parts":[[2021,10,15]],"date-time":"2021-10-15T18:32:31Z","timestamp":1634322751000},"page":"1027-1068","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":6,"title":["Decreasing minimization on M-convex sets: algorithms and applications"],"prefix":"10.1007","volume":"195","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-6161-4848","authenticated-orcid":false,"given":"Andr\u00e1s","family":"Frank","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1518-9152","authenticated-orcid":false,"given":"Kazuo","family":"Murota","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2021,10,15]]},"reference":[{"key":"1711_CR1","doi-asserted-by":"publisher","first-page":"1297","DOI":"10.1137\/060651136","volume":"23","author":"N Apollonio","year":"2009","unstructured":"Apollonio, N., Seb\u0151, A.: Minconvex factors of prescribed size in graphs. SIAM J. Discret. Math. 23, 1297\u20131310 (2009)","journal-title":"SIAM J. Discret. Math."},{"key":"1711_CR2","doi-asserted-by":"publisher","first-page":"726","DOI":"10.1287\/moor.2017.0881","volume":"43","author":"K B\u00e9rczi","year":"2018","unstructured":"B\u00e9rczi, K., Frank, A.: Supermodularity in unweighted graph optimization, Part I: Branchings and matchings. Math. Oper. Res. 43, 726\u2013753 (2018)","journal-title":"Math. Oper. Res."},{"key":"1711_CR3","unstructured":"Bern\u00e1th, A.: Personal communication (2021)"},{"key":"1711_CR4","doi-asserted-by":"publisher","first-page":"663","DOI":"10.1016\/j.disopt.2008.03.001","volume":"5","author":"A Bern\u00e1th","year":"2008","unstructured":"Bern\u00e1th, A., Iwata, S., Kir\u00e1ly, T., Kir\u00e1ly, Z., Szigeti, Z.: Recent results on well-balanced orientations. Discret. Optim. 5, 663\u2013676 (2008)","journal-title":"Discret. Optim."},{"key":"1711_CR5","doi-asserted-by":"crossref","unstructured":"Boesch, F., Tindell, R.: Robbins\u2019s theorem for mixed multigraphs. Amer. Math. Monthly 87, 716\u2013719 (1980)","DOI":"10.1080\/00029890.1980.11995131"},{"key":"1711_CR6","doi-asserted-by":"crossref","unstructured":"Bokal, D., Bre\u0161ar, B., Jerebic, J.: A generalization of Hungarian method and Hall\u2019s theorem with applications in wireless sensor networks. Discret. Appl. Math. 160, 460\u2013470 (2012)","DOI":"10.1016\/j.dam.2011.11.007"},{"key":"1711_CR7","doi-asserted-by":"publisher","first-page":"687","DOI":"10.7155\/jgaa.00435","volume":"21","author":"G Borradaile","year":"2017","unstructured":"Borradaile, G., Iglesias, J., Migler, T., Ochoa, A., Wilfong, G., Zhang, L.: Egalitarian graph orientations. J. Gr. Algorithms Appl. 21, 687\u2013708 (2017)","journal-title":"J. Gr. Algorithms Appl."},{"key":"1711_CR8","doi-asserted-by":"publisher","first-page":"625","DOI":"10.7155\/jgaa.00505","volume":"23","author":"G Borradaile","year":"2019","unstructured":"Borradaile, G., Migler, T., Wilfong, G.: Density decompositions of networks. J. Gr. Algorithms Appl. 23, 625\u2013651 (2019)","journal-title":"J. Gr. Algorithms Appl."},{"key":"1711_CR9","first-page":"69","volume-title":"Combinatorial Structures and Their Applications","author":"J Edmonds","year":"1970","unstructured":"Edmonds, J.: Submodular functions, matroids and certain polyhedra. In: Guy, R., Hanani, H., Sauer, N., Sch\u00f6nheim, J. (eds.) Combinatorial Structures and Their Applications, pp. 69\u201387. Gordon and Breach, New York (1970)"},{"key":"1711_CR10","first-page":"91","volume-title":"Combinatorial Algorithms","author":"J Edmonds","year":"1973","unstructured":"Edmonds, J.: Edge-disjoint branchings. In: Rustin, B. (ed.) Combinatorial Algorithms, pp. 91\u201396. Academic Press, New York (1973)"},{"key":"1711_CR11","doi-asserted-by":"publisher","first-page":"39","DOI":"10.1016\/S0167-5060(08)70817-3","volume":"14","author":"J Edmonds","year":"1979","unstructured":"Edmonds, J.: Matroid intersection. Ann. Discret. Math. 14, 39\u201349 (1979)","journal-title":"Ann. Discret. Math."},{"key":"1711_CR12","doi-asserted-by":"publisher","first-page":"909","DOI":"10.1287\/opre.34.6.909","volume":"34","author":"A Federgruen","year":"1986","unstructured":"Federgruen, A., Groenevelt, H.: The greedy procedure for resource allocation problems: necessary and sufficient conditions for optimality. Oper. Res. 34, 909\u2013918 (1986)","journal-title":"Oper. Res."},{"key":"1711_CR13","volume-title":"Flows in Networks","author":"LR Ford Jr","year":"1962","unstructured":"Ford, L.R., Jr., Fulkerson, D.R.: Flows in Networks. Princeton University Press, Princeton, NJ (1962)"},{"key":"1711_CR14","doi-asserted-by":"crossref","unstructured":"Frank, A.: On the orientation of graphs. J. Combin. Theory, Ser.\u00a0B 28, 251\u2013261 (1980)","DOI":"10.1016\/0095-8956(80)90071-4"},{"key":"1711_CR15","doi-asserted-by":"publisher","first-page":"22","DOI":"10.1137\/0405003","volume":"5","author":"A Frank","year":"1992","unstructured":"Frank, A.: Augmenting graphs to meet edge-connectivity requirements. SIAM J. Discret. Math. 5, 22\u201353 (1992)","journal-title":"SIAM J. Discret. Math."},{"key":"1711_CR16","volume-title":"Connections in Combinatorial Optimization","author":"A Frank","year":"2011","unstructured":"Frank, A.: Connections in Combinatorial Optimization. Oxford University Press, Oxford (2011)"},{"key":"1711_CR17","doi-asserted-by":"crossref","unstructured":"Frank, A., Jord\u00e1n, T.: Minimal edge-coverings of pairs of sets. J. Combin. Theory Ser.\u00a0B 65, 73\u2013110 (1995)","DOI":"10.1006\/jctb.1995.1044"},{"key":"1711_CR18","doi-asserted-by":"publisher","first-page":"87","DOI":"10.1007\/978-3-540-76796-1_6","volume-title":"Research Trends in Combinatorial Optimization","author":"A Frank","year":"2009","unstructured":"Frank, A., Kir\u00e1ly, T.: A survey on covering supermodular functions. In: Cook, W., Lov\u00e1sz, L., Vygen, J. (eds.) Research Trends in Combinatorial Optimization, pp. 87\u2013126. Springer, Berlin (2009)"},{"key":"1711_CR19","doi-asserted-by":"publisher","first-page":"385","DOI":"10.1016\/S0166-218X(02)00462-6","volume":"131","author":"A Frank","year":"2003","unstructured":"Frank, A., Kir\u00e1ly, T., Kir\u00e1ly, Z.: On the orientation of graphs and hypergraphs. Discret. Appl. Math. 131, 385\u2013400 (2003)","journal-title":"Discret. Appl. Math."},{"key":"1711_CR20","unstructured":"Frank, A., Murota, K.: Discrete decreasing minimization, Part\u00a0II: Views from discrete convex analysis. arXiv: 1808.08477 (2018)"},{"key":"1711_CR21","doi-asserted-by":"crossref","unstructured":"Frank, A., Murota, K.: Decreasing minimization on M-convex sets: Background and structures. Math. Program., to appear. arXiv: 2007.09616 (2020)","DOI":"10.1007\/s10107-021-01722-2"},{"key":"1711_CR22","unstructured":"Frank, A., Murota, K.: Fair integral flows. Submitted for publication. arXiv: 1907.02673 (2020)"},{"key":"1711_CR23","unstructured":"Frank, A., Murota, K.: Fair integral submodular flows. Submitted for publication. arXiv:2012.073252012, 07325 (2020)"},{"key":"1711_CR24","doi-asserted-by":"publisher","first-page":"489","DOI":"10.1007\/BF01589418","volume":"42","author":"A Frank","year":"1988","unstructured":"Frank, A., Tardos, \u00c9.: Generalized polymatroids and submodular flows. Math. Program. 42, 489\u2013563 (1988)","journal-title":"Math. Program."},{"key":"1711_CR25","doi-asserted-by":"publisher","first-page":"186","DOI":"10.1287\/moor.5.2.186","volume":"5","author":"S Fujishige","year":"1980","unstructured":"Fujishige, S.: Lexicographically optimal base of a polymatroid with respect to a weight vector. Math. Oper. Res. 5, 186\u2013196 (1980)","journal-title":"Math. Oper. Res."},{"key":"1711_CR26","doi-asserted-by":"publisher","first-page":"125","DOI":"10.1007\/BF02592217","volume":"29","author":"S Fujishige","year":"1984","unstructured":"Fujishige, S.: Structures of polyhedra determined by submodular functions on crossing families. Math. Program. 29, 125\u2013141 (1984)","journal-title":"Math. Program."},{"key":"1711_CR27","unstructured":"Fujishige, S.: Submodular Functions and Optimization, 2nd edn. Annals of Discrete Mathematics 58, Elsevier, Amsterdam (2005)"},{"key":"1711_CR28","doi-asserted-by":"crossref","unstructured":"Goemans, M.X., Gupta, S., Jaillet, P.: Discrete Newton\u2019s algorithm for parametric submodular function minimization. In: Eisenbrand, F., Koenemann, J. (eds.) Integer Programming and Combinatorial Optimization. Lecture Notes in Computer Science, vol.\u00a010328, pp.\u00a0212\u2013227 (2017)","DOI":"10.1007\/978-3-319-59250-3_18"},{"key":"1711_CR29","doi-asserted-by":"publisher","first-page":"290","DOI":"10.1016\/0016-0032(65)90340-6","volume":"279","author":"SL Hakimi","year":"1965","unstructured":"Hakimi, S.L.: On the degrees of the vertices of a directed graph. J. Frankl. Inst. 279, 290\u2013308 (1965)","journal-title":"J. Frankl. Inst."},{"key":"1711_CR30","doi-asserted-by":"publisher","first-page":"693","DOI":"10.2197\/ipsjdc.3.693","volume":"3","author":"Y Harada","year":"2007","unstructured":"Harada, Y., Ono, H., Sadakane, K., Yamashita, M.: Optimal balanced semi-matchings for weighted bipartite graphs. IPSJ Digit. Courier 3, 693\u2013702 (2007)","journal-title":"IPSJ Digit. Courier"},{"key":"1711_CR31","doi-asserted-by":"publisher","first-page":"53","DOI":"10.1016\/j.jalgor.2005.01.003","volume":"59","author":"NJA Harvey","year":"2006","unstructured":"Harvey, N.J.A., Ladner, R.E., Lov\u00e1sz, L., Tamir, T.: Semi-matchings for bipartite graphs and load balancing. J. Algorithms 59, 53\u201378 (2006)","journal-title":"J. Algorithms"},{"key":"1711_CR32","doi-asserted-by":"publisher","first-page":"257","DOI":"10.1007\/s10479-007-0172-6","volume":"153","author":"DS Hochbaum","year":"2007","unstructured":"Hochbaum, D.S.: Complexity and algorithms for nonlinear optimization problems. Ann. Oper. Res. 153, 257\u2013296 (2007)","journal-title":"Ann. Oper. Res."},{"key":"1711_CR33","doi-asserted-by":"publisher","first-page":"269","DOI":"10.1007\/BF01585561","volume":"69","author":"DS Hochbaum","year":"1995","unstructured":"Hochbaum, D.S., Hong, S.-P.: About strongly polynomial time algorithms for quadratic optimization over submodular constraints. Math. Program. 69, 269\u2013309 (1995)","journal-title":"Math. Program."},{"key":"1711_CR34","doi-asserted-by":"crossref","unstructured":"Hoffman, A.J.: Some recent applications of the theory of linear inequalities to extremal combinatorial analysis. In: Bellman, R., Hall, M., Jr. (eds.) Combinatorial Analysis (Proceedings of the Symposia of Applied Mathematics 10) pp.\u00a0113\u2013127. American Mathematical Society, Providence, Rhode Island (1960)","DOI":"10.1090\/psapm\/010\/0114759"},{"key":"1711_CR35","volume-title":"Resource Allocation Problems: Algorithmic Approaches","author":"T Ibaraki","year":"1988","unstructured":"Ibaraki, T., Katoh, N.: Resource Allocation Problems: Algorithmic Approaches. MIT Press, Boston (1988)"},{"key":"1711_CR36","doi-asserted-by":"publisher","first-page":"761","DOI":"10.1145\/502090.502096","volume":"48","author":"S Iwata","year":"2001","unstructured":"Iwata, S., Fleischer, L., Fujishige, S.: A combinatorial, strongly polynomial-time algorithm for minimizing submodular functions. J. ACM 48, 761\u2013777 (2001)","journal-title":"J. ACM"},{"key":"1711_CR37","doi-asserted-by":"crossref","unstructured":"Jiang, H.: Minimizing convex functions with integral minimizers. In: Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA), SIAM, pp.\u00a0976\u2013985 (2021)","DOI":"10.1137\/1.9781611976465.61"},{"key":"1711_CR38","first-page":"159","volume-title":"Handbook of Combinatorial Optimization","author":"N Katoh","year":"1998","unstructured":"Katoh, N., Ibaraki, T.: Resource allocation problems. In: Du, D.-Z., Pardalos, P.M. (eds.) Handbook of Combinatorial Optimization, vol. 2, pp. 159\u2013260. Kluwer Academic Publishers, Boston (1998)"},{"key":"1711_CR39","doi-asserted-by":"publisher","first-page":"2897","DOI":"10.1007\/978-1-4419-7997-1_44","volume-title":"Handbook of Combinatorial Optimization","author":"N Katoh","year":"2013","unstructured":"Katoh, N., Shioura, A., Ibaraki, T.: Resource allocation problems. In: Pardalos, P.M., Du, D.-Z., Graham, R.L. (eds.) Handbook of Combinatorial Optimization, vol. 5, 2nd edn., pp. 2897\u20132988. Springer, Berlin (2013)","edition":"2"},{"key":"1711_CR40","doi-asserted-by":"publisher","first-page":"559","DOI":"10.7151\/dmgt.1694","volume":"33","author":"J Katreni\u010d","year":"2013","unstructured":"Katreni\u010d, J., Semani\u0161in, G.: Maximum semi-matching problem in bipartite graphs. Discussiones Mathematicae Gr. Theory 33, 559\u2013569 (2013)","journal-title":"Discussiones Mathematicae Gr. Theory"},{"key":"1711_CR41","doi-asserted-by":"crossref","unstructured":"Kir\u00e1ly, T., Lau, L.-C.: Approximate min-max theorems for Steiner rooted-orientations of graphs and hypergraphs. J. Combin. Theory Ser.\u00a0B 98, 1233\u20131252 (2008)","DOI":"10.1016\/j.jctb.2008.01.006"},{"key":"1711_CR42","doi-asserted-by":"publisher","first-page":"535","DOI":"10.1016\/j.orl.2016.05.013","volume":"44","author":"A Levin","year":"2016","unstructured":"Levin, A., Onn, S.: Shifted matroid optimization. Oper. Res. Lett. 44, 535\u2013539 (2016)","journal-title":"Oper. Res. Lett."},{"key":"1711_CR43","doi-asserted-by":"publisher","first-page":"97","DOI":"10.1007\/BF01585506","volume":"7","author":"N Megiddo","year":"1974","unstructured":"Megiddo, N.: Optimal flows in networks with multiple sources and sinks. Math. Program. 7, 97\u2013107 (1974)","journal-title":"Math. Program."},{"key":"1711_CR44","doi-asserted-by":"publisher","first-page":"407","DOI":"10.1090\/S0002-9904-1977-14298-5","volume":"83","author":"N Megiddo","year":"1977","unstructured":"Megiddo, N.: A good algorithm for lexicographically optimal flows in multi-terminal networks. Bull. Am. Math. Soc. 83, 407\u2013409 (1977)","journal-title":"Bull. Am. Math. Soc."},{"key":"1711_CR45","doi-asserted-by":"publisher","first-page":"633","DOI":"10.1137\/080736156","volume":"21","author":"S Moriguchi","year":"2011","unstructured":"Moriguchi, S., Shioura, A., Tsuchimura, N.: M-convex function minimization by continuous relaxation approach\u2013Proximity theorem and algorithm. SIAM J. Optim. 21, 633\u2013668 (2011)","journal-title":"SIAM J. Optim."},{"key":"1711_CR46","doi-asserted-by":"publisher","first-page":"313","DOI":"10.1007\/BF02680565","volume":"83","author":"K Murota","year":"1998","unstructured":"Murota, K.: Discrete convex analysis. Math. Program. 83, 313\u2013371 (1998)","journal-title":"Math. Program."},{"key":"1711_CR47","doi-asserted-by":"publisher","DOI":"10.1137\/1.9780898718508","volume-title":"Discrete Convex Analysis","author":"K Murota","year":"2003","unstructured":"Murota, K.: Discrete Convex Analysis. Society for Industrial and Applied Mathematics, Philadelphia (2003)"},{"key":"1711_CR48","doi-asserted-by":"crossref","unstructured":"Nash-Williams, C.St.J.A.: On orientations, connectivity and odd vertex pairings in finite graphs. Can. J. Math. 12, 555\u2013567 (1960)","DOI":"10.4153\/CJM-1960-049-6"},{"key":"1711_CR49","doi-asserted-by":"publisher","first-page":"237","DOI":"10.1007\/s10107-007-0189-2","volume":"118","author":"JB Orlin","year":"2009","unstructured":"Orlin, J.B.: A faster strongly polynomial time algorithm for submodular function minimization. Math. Program. Ser. A 118, 237\u2013251 (2009)","journal-title":"Math. Program. Ser. A"},{"key":"1711_CR50","doi-asserted-by":"publisher","first-page":"1311","DOI":"10.1007\/978-1-4419-7997-1_62","volume-title":"Handbook of Combinatorial Optimization","author":"T Radzik","year":"2013","unstructured":"Radzik, T.: Fractional combinatorial optimization. In: Pardalos, P.M., Du, D.-Z., Graham, R.L. (eds.) Handbook of Combinatorial Optimization, 2nd edn., pp. 1311\u20131355. Springer, New York (2013)","edition":"2"},{"key":"1711_CR51","doi-asserted-by":"publisher","first-page":"281","DOI":"10.2307\/2303897","volume":"46","author":"HE Robbins","year":"1939","unstructured":"Robbins, H.E.: A theorem on graphs with an application to a problem of traffic control. Amer. Math. Mon. 46, 281\u2013283 (1939)","journal-title":"Amer. Math. Mon."},{"key":"1711_CR52","doi-asserted-by":"publisher","first-page":"346","DOI":"10.1006\/jctb.2000.1989","volume":"80","author":"A Schrijver","year":"2000","unstructured":"Schrijver, A.: A combinatorial algorithm minimizing submodular functions in strongly polynomial time. J. Combin. Theory Ser. B 80, 346\u2013355 (2000)","journal-title":"J. Combin. Theory Ser. B"},{"key":"1711_CR53","volume-title":"Combinatorial Optimization: Polyhedra and Efficiency","author":"A Schrijver","year":"2003","unstructured":"Schrijver, A.: Combinatorial Optimization: Polyhedra and Efficiency. Springer, Heidelberg (2003)"},{"key":"1711_CR54","doi-asserted-by":"publisher","first-page":"247","DOI":"10.1007\/BF02579369","volume":"5","author":"\u00c9 Tardos","year":"1985","unstructured":"Tardos, \u00c9.: A strongly polynomial minimum cost circulation algorithm. Combinatorica 5, 247\u2013255 (1985)","journal-title":"Combinatorica"},{"key":"1711_CR55","doi-asserted-by":"publisher","first-page":"305","DOI":"10.1287\/opre.26.2.305","volume":"26","author":"DM Topkis","year":"1978","unstructured":"Topkis, D.M.: Minimizing a submodular function on a lattice. Oper. Res. 26, 305\u2013321 (1978)","journal-title":"Oper. Res."},{"key":"1711_CR56","doi-asserted-by":"crossref","unstructured":"Zhou, H., Hou, X.: Strongly connected orientation with minimum lexicographic order of indegrees. arXiv:2103.01017 (2021)","DOI":"10.1142\/S0129054122500046"}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-021-01711-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10107-021-01711-5\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-021-01711-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,10,21]],"date-time":"2022-10-21T15:37:01Z","timestamp":1666366621000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10107-021-01711-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,10,15]]},"references-count":56,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2022,9]]}},"alternative-id":["1711"],"URL":"https:\/\/doi.org\/10.1007\/s10107-021-01711-5","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"value":"0025-5610","type":"print"},{"value":"1436-4646","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,10,15]]},"assertion":[{"value":"18 July 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"22 September 2021","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"15 October 2021","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}