{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,11]],"date-time":"2025-09-11T07:12:47Z","timestamp":1757574767432},"reference-count":41,"publisher":"Wiley","issue":"4","license":[{"start":{"date-parts":[[2006,10,11]],"date-time":"2006-10-11T00:00:00Z","timestamp":1160524800000},"content-version":"vor","delay-in-days":6523,"URL":"http:\/\/onlinelibrary.wiley.com\/termsAndConditions#vor"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Networks"],"published-print":{"date-parts":[[1988,12]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We consider the polymatroidal flow network model which incorporates two important extensions of the standard maximal flow problem: general concave objective functions of the vector of supplies to a collection of sinks, as well as polymatroidal capacity restrictions on sets of arcs emanating from or pointing to a common node. A number of important applications are reviewed. We show that in this general model the set of feasible supply vectors is itself a polymatroid, and that an optimal solution may be determined by at most 2|V<jats:sup>*<\/jats:sup>| \u2014 1 maximum flow computations and optimizations of the objective over a single budget constraint, where |V<jats:sup>*<\/jats:sup>| is the number of sinks. Also, it is shown that for the most common types of polymatroidal structures an equivalent flow network can be constructed on an expanded graph but with capacity restrictions on individual arcs only. This transformation allows for the use of classical maximum flow procedures resulting in an often dramatic reduction in complexity.<\/jats:p>","DOI":"10.1002\/net.3230180404","type":"journal-article","created":{"date-parts":[[2007,5,12]],"date-time":"2007-05-12T01:49:50Z","timestamp":1178934590000},"page":"285-302","source":"Crossref","is-referenced-by-count":15,"title":["Polymatroidal flow network models with multiple sinks"],"prefix":"10.1002","volume":"18","author":[{"given":"A.","family":"Federgruen","sequence":"first","affiliation":[]},{"given":"H.","family":"Groenevelt","sequence":"additional","affiliation":[]}],"member":"311","published-online":{"date-parts":[[2006,10,11]]},"reference":[{"key":"e_1_2_1_2_2","volume-title":"Strokes in Linear and Nonlinear Programming","author":"Arrow K.","year":"1958"},{"key":"e_1_2_1_3_2","first-page":"72","volume-title":"Statistical Inference under Order Restrictions","author":"Barlow R. E.","year":"1972"},{"key":"e_1_2_1_4_2","doi-asserted-by":"publisher","DOI":"10.1287\/moor.10.3.367"},{"key":"e_1_2_1_5_2","doi-asserted-by":"publisher","DOI":"10.1287\/opre.27.2.324"},{"key":"e_1_2_1_6_2","doi-asserted-by":"publisher","DOI":"10.1287\/opre.27.2.341"},{"key":"e_1_2_1_7_2","doi-asserted-by":"publisher","DOI":"10.1057\/jors.1955.17"},{"key":"e_1_2_1_8_2","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(84)90023-6"},{"key":"e_1_2_1_9_2","doi-asserted-by":"publisher","DOI":"10.1287\/opre.34.6.909"},{"key":"e_1_2_1_10_2","doi-asserted-by":"publisher","DOI":"10.1287\/mnsc.32.3.341"},{"key":"e_1_2_1_11_2","doi-asserted-by":"publisher","DOI":"10.1287\/opre.34.2.218"},{"key":"e_1_2_1_12_2","unstructured":"A.FedergruenandY.Zheng Multi\u2010item multi\u2010stage deterministic production\/inventory systems with joint setup costs (in preparation) (1988)."},{"key":"e_1_2_1_13_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF02591716"},{"key":"e_1_2_1_14_2","doi-asserted-by":"publisher","DOI":"10.1515\/9781400875184"},{"key":"e_1_2_1_15_2","doi-asserted-by":"crossref","unstructured":"G. N.FredericksonandD. B.Johnson The complexity of selection and ranking in X + Y and matrices with sorted columns.J. Computer System Sci.(1982)197\u2013208.","DOI":"10.1016\/0022-0000(82)90048-4"},{"key":"e_1_2_1_16_2","doi-asserted-by":"publisher","DOI":"10.1287\/moor.5.2.186"},{"key":"e_1_2_1_17_2","unstructured":"H.Groenevelt Resource allocation problem with decreasing marginal returns to scale. Ph.D. Dissertation Columbia University New York 1984."},{"key":"e_1_2_1_18_2","unstructured":"[a]H.Groenevelt Two algorithms for maximizing a separable concave function over a polymatroid feasible region. Working Paper Graduate School of Management University of Rochester (1985)."},{"key":"e_1_2_1_19_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579273"},{"key":"e_1_2_1_20_2","volume-title":"D. Fernandez\u2010Baca, Fast Algorithms for Bipartite Network Flow","author":"Gusfield D.","year":"1985"},{"key":"e_1_2_1_21_2","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230120102"},{"key":"e_1_2_1_22_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01583798"},{"key":"e_1_2_1_23_2","volume-title":"Combinatorial Optimization: Networks and Matroids","author":"Lawler E. L.","year":"1976"},{"key":"e_1_2_1_24_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-5060(08)70323-6"},{"key":"e_1_2_1_25_2","unstructured":"E. L.Lawler Generalizations of the polymatroidal network flow model. Report BW 158 Mathematisch Centrum Amsterdam (1982)."},{"key":"e_1_2_1_26_2","doi-asserted-by":"publisher","DOI":"10.1287\/moor.7.3.334"},{"key":"e_1_2_1_27_2","first-page":"189","article-title":"Flow network formulations of polymatroid optimization problems","volume":"16","author":"Lawler E. L.","year":"1982","journal-title":"Annals of Discr. Math."},{"key":"e_1_2_1_28_2","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(78)90016-9"},{"key":"e_1_2_1_29_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-94-009-7801-0_5"},{"key":"e_1_2_1_30_2","doi-asserted-by":"publisher","DOI":"10.1145\/322326.322337"},{"key":"e_1_2_1_31_2","doi-asserted-by":"publisher","DOI":"10.1287\/opre.33.6.1316"},{"key":"e_1_2_1_32_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01585506"},{"key":"e_1_2_1_33_2","volume-title":"Combinatorial Optimization: Algorithms and Complexity","author":"Papadimitriou C. H.","year":"1982"},{"key":"e_1_2_1_34_2","doi-asserted-by":"publisher","DOI":"10.1287\/moor.11.4.699"},{"key":"e_1_2_1_35_2","doi-asserted-by":"publisher","DOI":"10.1287\/opre.23.2.283"},{"key":"e_1_2_1_36_2","doi-asserted-by":"publisher","DOI":"10.1287\/moor.11.2.362"},{"key":"e_1_2_1_37_2","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230130106"},{"key":"e_1_2_1_38_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF02591887"},{"key":"e_1_2_1_39_2","doi-asserted-by":"publisher","DOI":"10.1287\/mnsc.17.9.547"},{"key":"e_1_2_1_40_2","volume-title":"Principles of Operations Research","author":"Wagner H.","year":"1975"},{"key":"e_1_2_1_41_2","unstructured":"Y. S.Zheng Replenishment Strategies for Production\/Distribution Systems with General Joint Setup Costs Ph.D. dissertation Columbia University New York (1987)."},{"key":"e_1_2_1_42_2","doi-asserted-by":"publisher","DOI":"10.1287\/mnsc.26.1.34"}],"container-title":["Networks"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.wiley.com\/onlinelibrary\/tdm\/v1\/articles\/10.1002%2Fnet.3230180404","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/net.3230180404","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,10,22]],"date-time":"2023-10-22T01:22:16Z","timestamp":1697937736000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1002\/net.3230180404"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1988,12]]},"references-count":41,"journal-issue":{"issue":"4","published-print":{"date-parts":[[1988,12]]}},"alternative-id":["10.1002\/net.3230180404"],"URL":"https:\/\/doi.org\/10.1002\/net.3230180404","archive":["Portico"],"relation":{},"ISSN":["0028-3045","1097-0037"],"issn-type":[{"value":"0028-3045","type":"print"},{"value":"1097-0037","type":"electronic"}],"subject":[],"published":{"date-parts":[[1988,12]]}}}