{"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":1772170984570,"version":"3.50.1"},"reference-count":38,"publisher":"Springer Science and Business Media LLC","issue":"1-2","license":[{"start":{"date-parts":[[2021,10,27]],"date-time":"2021-10-27T00:00:00Z","timestamp":1635292800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2021,10,27]],"date-time":"2021-10-27T00:00:00Z","timestamp":1635292800000},"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-01722-2","type":"journal-article","created":{"date-parts":[[2021,10,27]],"date-time":"2021-10-27T14:02:58Z","timestamp":1635343378000},"page":"977-1025","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":9,"title":["Decreasing minimization on M-convex sets: background and structures"],"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,27]]},"reference":[{"key":"1722_CR1","doi-asserted-by":"publisher","first-page":"189","DOI":"10.1007\/s00453-004-1085-2","volume":"39","author":"RK Ahuja","year":"2004","unstructured":"Ahuja, R.K., Hochbaum, D.S., Orlin, J.B.: A cut-based algorithm for the nonlinear dual of the minimum cost network flow problem. Algorithmica 39, 189\u2013208 (2004)","journal-title":"Algorithmica"},{"key":"1722_CR2","unstructured":"Arnold, B.C., Sarabia, J.M.: Majorization and the Lorenz Order with Applications in Applied Mathematics and Economics, Springer International Publishing, Cham (2018), (1st edn., 1987)"},{"key":"1722_CR3","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. Discrete Appl. Math. 160, 460\u2013470 (2012)","DOI":"10.1016\/j.dam.2011.11.007"},{"key":"1722_CR4","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. Graph Algorithms Appl. 21, 687\u2013708 (2017)","journal-title":"J. Graph Algorithms Appl."},{"key":"1722_CR5","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. Graph Algorithms Appl. 23, 625\u2013651 (2019)","journal-title":"J. Graph Algorithms Appl."},{"key":"1722_CR6","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":"1722_CR7","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":"1722_CR8","doi-asserted-by":"publisher","first-page":"251","DOI":"10.1016\/0095-8956(80)90071-4","volume":"28","author":"A Frank","year":"1980","unstructured":"Frank, A.: On the orientation of graphs. J. Combin. Theory Ser. B 28, 251\u2013261 (1980)","journal-title":"J. Combin. Theory Ser. B"},{"key":"1722_CR9","volume-title":"Connections in Combinatorial Optimization","author":"A Frank","year":"2011","unstructured":"Frank, A.: Connections in Combinatorial Optimization. Oxford University Press, Oxford (2011)"},{"key":"1722_CR10","unstructured":"Frank, A., Murota, K.: Discrete decreasing minimization, Part\u00a0II: Views from discrete convex analysis. arXiv: 1808.08477 (2018)"},{"key":"1722_CR11","doi-asserted-by":"publisher","unstructured":"Frank, A., Murota, K.: Decreasing minimization on M-convex sets: Algorithms and applications. Mathematical Programming, published online (October 15, 2021). https:\/\/doi.org\/10.1007\/s10107-021-01711-5","DOI":"10.1007\/s10107-021-01711-5"},{"key":"1722_CR12","unstructured":"Frank, A., Murota, K.: A discrete convex min-max formula for box-TDI polyhedra. Mathematics of Operations Research, to appear. arXiv:2007.03507"},{"key":"1722_CR13","unstructured":"Frank, A., Murota, K.: Fair integral flows. Submitted for publication. arXiv: 1907.02673v3 (2020)"},{"key":"1722_CR14","unstructured":"Frank, A., Murota, K.: Fair integral submodular flows. Submitted for publication. arXiv: 2012.07325 (2020)"},{"key":"1722_CR15","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":"1722_CR16","unstructured":"Fujishige, S.: Submodular Functions and Optimization, 2nd edn. Annals of Discrete Mathematics 58. Elsevier, Amsterdam (2005)"},{"key":"1722_CR17","doi-asserted-by":"publisher","first-page":"127","DOI":"10.1007\/978-3-540-76796-1_7","volume-title":"Research Trends in Combinatorial Optimization","author":"S Fujishige","year":"2009","unstructured":"Fujishige, S.: Theory of principal partitions revisited. In: Cook, W., Lov\u00e1sz, L., Vygen, J. (eds.) Research Trends in Combinatorial Optimization, pp. 127\u2013162. Springer, Berlin (2009)"},{"key":"1722_CR18","doi-asserted-by":"crossref","unstructured":"Ghodsi, A., Zaharia, M., Shenker, S., Stoica, I.: Choosy: Max-min fair sharing for datacenter jobs with constraints. In: EuroSys \u201913 Proceedings of the 8th ACM European Conference on Computer Systems, pp.\u00a0365\u2013378, ACM New York, NY (2013)","DOI":"10.1145\/2465351.2465387"},{"key":"1722_CR19","doi-asserted-by":"publisher","first-page":"227","DOI":"10.1016\/0377-2217(91)90300-K","volume":"54","author":"H Groenevelt","year":"1991","unstructured":"Groenevelt, H.: Two algorithms for maximizing a separable concave function over a polymatroid feasible region. Eur. J. Oper. Res. 54, 227\u2013236 (1991)","journal-title":"Eur. J. Oper. Res."},{"key":"1722_CR20","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 Digital Courier 3, 693\u2013702 (2007)","journal-title":"IPSJ Digital Courier"},{"key":"1722_CR21","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":"1722_CR22","doi-asserted-by":"publisher","first-page":"291","DOI":"10.1016\/S0377-2217(02)00071-1","volume":"140","author":"DS Hochbaum","year":"2002","unstructured":"Hochbaum, D.S.: Solving integer programs over monotone inequalities in three variables: a framework for half integrality and good approximations. Eur. J. Oper. Res. 140, 291\u2013321 (2002)","journal-title":"Eur. J. Oper. Res."},{"key":"1722_CR23","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":"1722_CR24","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":"1722_CR25","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":"1722_CR26","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":"1722_CR27","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":"1722_CR28","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 Graph Theory 33, 559\u2013569 (2013)","journal-title":"Discussiones Mathematicae Graph Theory"},{"key":"1722_CR29","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":"1722_CR30","doi-asserted-by":"publisher","first-page":"235","DOI":"10.1007\/978-3-642-68874-4_10","volume-title":"Mathematical Programming-The State of the Art","author":"L Lov\u00e1sz","year":"1983","unstructured":"Lov\u00e1sz, L.: Submodular functions and convexity. In: Bachem, A., Gr\u00f6tschel, M., Korte, B. (eds.) Mathematical Programming-The State of the Art, pp. 235\u2013257. Springer, Berlin (1983)"},{"key":"1722_CR31","doi-asserted-by":"crossref","unstructured":"Marshall, A.W., Olkin, I., Arnold, B.C.: Inequalities: Theory of Majorization and Iis Applications, 2nd edn. Springer, New York (2011), (1st edn., 1979)","DOI":"10.1007\/978-0-387-68276-1_21"},{"key":"1722_CR32","unstructured":"Maruyama, F.: A unified study on problems in information theory via polymatroids. Graduation Thesis, University of Tokyo, Japan (1978) (in Japanese)"},{"key":"1722_CR33","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":"1722_CR34","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":"1722_CR35","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":"1722_CR36","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":"1722_CR37","doi-asserted-by":"crossref","unstructured":"Nagano, K.: On convex minimization over base polytopes. In: Fischetti, M., Williamson, D.P. (eds.): Integer Programming and Combinatorial Optimization. Lecture Notes in Computer Science, vol.\u00a04513, pp.\u00a0252\u2013266 (2007)","DOI":"10.1007\/978-3-540-72792-7_20"},{"key":"1722_CR38","doi-asserted-by":"publisher","first-page":"583","DOI":"10.1287\/moor.20.3.583","volume":"20","author":"A Tamir","year":"1995","unstructured":"Tamir, A.: Least majorized elements and generalized polymatroids. Math. Oper. Res. 20, 583\u2013589 (1995)","journal-title":"Math. Oper. Res."}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-021-01722-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10107-021-01722-2\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-021-01722-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,10,21]],"date-time":"2022-10-21T15:37:50Z","timestamp":1666366670000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10107-021-01722-2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,10,27]]},"references-count":38,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2022,9]]}},"alternative-id":["1722"],"URL":"https:\/\/doi.org\/10.1007\/s10107-021-01722-2","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"value":"0025-5610","type":"print"},{"value":"1436-4646","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,10,27]]},"assertion":[{"value":"18 July 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"6 October 2021","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"27 October 2021","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}