{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:24:06Z","timestamp":1740108246521,"version":"3.37.3"},"reference-count":38,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2017,7,28]],"date-time":"2017-07-28T00:00:00Z","timestamp":1501200000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Math Meth Oper Res"],"published-print":{"date-parts":[[2018,2]]},"DOI":"10.1007\/s00186-017-0604-2","type":"journal-article","created":{"date-parts":[[2017,7,28]],"date-time":"2017-07-28T02:59:24Z","timestamp":1501210764000},"page":"19-50","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["A generalized approximation framework for fractional network flow and packing problems"],"prefix":"10.1007","volume":"87","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-0544-4247","authenticated-orcid":false,"given":"Michael","family":"Holzhauser","sequence":"first","affiliation":[],"role":[{"role":"author","vocab":"crossref"}]},{"given":"Sven O.","family":"Krumke","sequence":"additional","affiliation":[],"role":[{"role":"author","vocab":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2017,7,28]]},"reference":[{"issue":"2","key":"604_CR1","doi-asserted-by":"crossref","first-page":"89","DOI":"10.1002\/net.3230250207","volume":"25","author":"RK Ahuja","year":"1995","unstructured":"Ahuja RK, Orlin JB (1995) A capacity scaling algorithm for the constrained maximum flow problem. Networks 25(2):89\u201398","journal-title":"Networks"},{"key":"604_CR2","volume-title":"Potential function methods for approximately solving linear programming problems: theory and practice","author":"D Bienstock","year":"2006","unstructured":"Bienstock D (2006) Potential function methods for approximately solving linear programming problems: theory and practice, vol 53. Springer, New York"},{"issue":"4","key":"604_CR3","doi-asserted-by":"crossref","first-page":"825","DOI":"10.1137\/S0097539705447293","volume":"35","author":"D Bienstock","year":"2006","unstructured":"Bienstock D, Iyengar G (2006) Approximating fractional packings and coverings in o (1\/epsilon) iterations. SIAM J Comput 35(4):825\u2013854","journal-title":"SIAM J Comput"},{"issue":"4","key":"604_CR4","doi-asserted-by":"crossref","first-page":"1138","DOI":"10.1016\/j.cor.2006.07.009","volume":"35","author":"C \u00c7al\u0131\u015fkan","year":"2008","unstructured":"\u00c7al\u0131\u015fkan C (2008) A double scaling algorithm for the constrained maximum flow problem. Comput Oper Res 35(4):1138\u20131150","journal-title":"Comput Oper Res"},{"issue":"3","key":"604_CR5","doi-asserted-by":"crossref","first-page":"229","DOI":"10.1002\/net.20263","volume":"53","author":"C \u00c7al\u0131\u015fkan","year":"2009","unstructured":"\u00c7al\u0131\u015fkan C (2009) On a capacity scaling algorithm for the constrained maximum flow problem. Networks 53(3):229\u2013230","journal-title":"Networks"},{"issue":"11","key":"604_CR6","doi-asserted-by":"crossref","first-page":"2634","DOI":"10.1016\/j.cor.2012.01.010","volume":"39","author":"C \u00c7al\u0131\u015fkan","year":"2012","unstructured":"\u00c7al\u0131\u015fkan C (2012) A faster polynomial algorithm for the constrained maximum flow problem. Comput Oper Res 39(11):2634\u20132641","journal-title":"Comput Oper Res"},{"issue":"6","key":"604_CR7","doi-asserted-by":"crossref","first-page":"1028","DOI":"10.1145\/355541.355562","volume":"47","author":"B Chazelle","year":"2000","unstructured":"Chazelle B (2000) A minimum spanning tree algorithm with inverse-ackermann type complexity. JACM 47(6):1028\u20131047","journal-title":"JACM"},{"key":"604_CR8","volume-title":"Maximizing concave functions in fixed dimension","author":"E Cohen","year":"1990","unstructured":"Cohen E, Megiddo N (1990) Maximizing concave functions in fixed dimension. World Scientific, Singapore"},{"issue":"6","key":"604_CR9","doi-asserted-by":"crossref","first-page":"1313","DOI":"10.1137\/S0097539791256325","volume":"23","author":"E Cohen","year":"1994","unstructured":"Cohen E, Megiddo N (1994) Improved algorithms for linear inequalities with two variables per inequality. SIAM J Comput 23(6):1313\u20131347","journal-title":"SIAM J Comput"},{"issue":"1","key":"604_CR10","doi-asserted-by":"crossref","first-page":"200","DOI":"10.1145\/7531.7537","volume":"34","author":"R Cole","year":"1987","unstructured":"Cole R (1987) Slowing down sorting networks to obtain faster sorting algorithms. JACM 34(1):200\u2013208","journal-title":"JACM"},{"issue":"2","key":"604_CR11","doi-asserted-by":"crossref","first-page":"161","DOI":"10.1016\/0095-8956(84)90023-6","volume":"36","author":"WH Cunningham","year":"1984","unstructured":"Cunningham WH (1984) Testing membership in matroid polyhedra. J Comb Theory B 36(2):161\u2013188","journal-title":"J Comb Theory B"},{"issue":"1","key":"604_CR12","doi-asserted-by":"crossref","first-page":"269","DOI":"10.1007\/BF01386390","volume":"1","author":"EW Dijkstra","year":"1959","unstructured":"Dijkstra EW (1959) A note on two problems in connexion with graphs. Numer Math 1(1):269\u2013271","journal-title":"Numer Math"},{"issue":"4","key":"604_CR13","doi-asserted-by":"crossref","first-page":"505","DOI":"10.1137\/S0895480199355754","volume":"13","author":"LK Fleischer","year":"2000","unstructured":"Fleischer LK (2000) Approximating fractional multicommodity flow independent of the number of commodities. SIAM J Discrete Math 13(4):505\u2013520","journal-title":"SIAM J Discrete Math"},{"issue":"2","key":"604_CR14","doi-asserted-by":"crossref","first-page":"215","DOI":"10.1007\/s101070100238","volume":"91","author":"LK Fleischer","year":"2002","unstructured":"Fleischer LK, Wayne KD (2002) Fast and simple approximation schemes for generalized flow. Math Program 91(2):215\u2013238","journal-title":"Math Program"},{"issue":"1\u20132","key":"604_CR15","first-page":"83","volume":"82","author":"HN Gabow","year":"1998","unstructured":"Gabow HN, Manu KS (1998) Packing algorithms for arborescences (and spanning trees) in capacitated graphs. Math Program 82(1\u20132):83\u2013109","journal-title":"Math Program"},{"key":"604_CR16","volume-title":"Computers and intractability\u2014a guide to the theory of $${\\cal{N}}{\\cal{P}}$$ N","author":"MR Garey","year":"1979","unstructured":"Garey MR, Johnson DS (1979) Computers and intractability\u2014a guide to the theory of \n                        $${\\cal{N}}{\\cal{P}}$$\n                        \n                            \n                                \n                                    N\n                                    P\n                                \n                            \n                        \n                    -completeness. W. H. Freeman and Company, New York"},{"issue":"2","key":"604_CR17","doi-asserted-by":"crossref","first-page":"630","DOI":"10.1137\/S0097539704446232","volume":"37","author":"N Garg","year":"2007","unstructured":"Garg N, Koenemann J (2007) Faster and simpler algorithms for multicommodity flow and other fractional packing problems. SIAM J Comput 37(2):630\u2013652","journal-title":"SIAM J Comput"},{"issue":"1","key":"604_CR18","doi-asserted-by":"crossref","first-page":"86","DOI":"10.1137\/0804004","volume":"4","author":"MD Grigoriadis","year":"1994","unstructured":"Grigoriadis MD, Khachiyan LG (1994) Fast approximation schemes for convex programs with many blocks and coupling constraints. SIAM J Optim 4(1):86\u2013107","journal-title":"SIAM J Optim"},{"issue":"2","key":"604_CR19","doi-asserted-by":"crossref","first-page":"321","DOI":"10.1287\/moor.21.2.321","volume":"21","author":"MD Grigoriadis","year":"1996","unstructured":"Grigoriadis MD, Khachiyan LG (1996) Coordination complexity of parallel price-directive decomposition. Math Oper Res 21(2):321\u2013340","journal-title":"Math Oper Res"},{"key":"604_CR20","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-78240-4","volume-title":"Geometric algorithms and combinatorial optimization, volume 2 of algorithms and combinatorics","author":"M Gr\u00f6tschel","year":"1993","unstructured":"Gr\u00f6tschel M, Lov\u00e1sz L, Schrijver A (1993) Geometric algorithms and combinatorial optimization, volume 2 of algorithms and combinatorics. Springer, Berlin"},{"issue":"1","key":"604_CR21","doi-asserted-by":"crossref","first-page":"36","DOI":"10.1287\/moor.17.1.36","volume":"17","author":"R Hassin","year":"1992","unstructured":"Hassin R (1992) Approximation schemes for the restricted shortest path problem. Math Oper Res 17(1):36\u201342","journal-title":"Math Oper Res"},{"doi-asserted-by":"crossref","unstructured":"Holzhauser M, Krumke SO, Thielen C (2016) Budget-constrained minimum cost flows. J Comb Optim 31(4):1720\u20131745","key":"604_CR22","DOI":"10.1007\/s10878-015-9865-y"},{"doi-asserted-by":"publisher","unstructured":"Holzhauser M, Krumke SO, Thielen C (2017a) On the complexity and approximability of budget-constrained minimum cost flows. Inf Process Lett 126: 24\u201329. doi:\n                        10.1016\/j.ipl.2017.06.003","key":"604_CR23","DOI":"10.1016\/j.ipl.2017.06.003"},{"doi-asserted-by":"publisher","unstructured":"Holzhauser M, Krumke SO, Thielen C (2017b) Maximum flows in generalized processing networks. J Comb Optim 33(4): 1226\u20131256. doi:\n                        10.1007\/s10878-016-0031-y","key":"604_CR24","DOI":"10.1007\/s10878-016-0031-y"},{"issue":"1","key":"604_CR25","first-page":"13","volume":"4","author":"G Karakostas","year":"2008","unstructured":"Karakostas G (2008) Faster approximation schemes for fractional multicommodity flow problems. ACM Trans Algorithms (TALG) 4(1):13","journal-title":"ACM Trans Algorithms (TALG)"},{"issue":"3","key":"604_CR26","doi-asserted-by":"crossref","first-page":"309","DOI":"10.1016\/0012-365X(78)90011-0","volume":"23","author":"RM Karp","year":"1978","unstructured":"Karp RM (1978) A characterization of the minimum cycle mean in a digraph. Discrete Math 23(3):309\u2013311","journal-title":"Discrete Math"},{"key":"604_CR27","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-540-24777-7","volume-title":"Knapsack problems","author":"H Kellerer","year":"2004","unstructured":"Kellerer H, Pferschy U, Pisinger D (2004) Knapsack problems. Springer, Berlin"},{"key":"604_CR28","volume-title":"Combinatorial optimization: networks and matroids","author":"EL Lawler","year":"2001","unstructured":"Lawler EL (2001) Combinatorial optimization: networks and matroids. Courier Corporation, New York"},{"issue":"4","key":"604_CR29","doi-asserted-by":"crossref","first-page":"414","DOI":"10.1287\/moor.4.4.414","volume":"4","author":"N Megiddo","year":"1979","unstructured":"Megiddo N (1979) Combinatorial optimization with rational objective functions. Math Oper Res 4(4):414\u2013424","journal-title":"Math Oper Res"},{"issue":"4","key":"604_CR30","doi-asserted-by":"crossref","first-page":"852","DOI":"10.1145\/2157.322410","volume":"30","author":"N Megiddo","year":"1983","unstructured":"Megiddo N (1983) Applying parallel computation algorithms in the design of serial algorithms. JACM 30(4):852\u2013865","journal-title":"JACM"},{"issue":"1","key":"604_CR31","doi-asserted-by":"crossref","first-page":"135","DOI":"10.1006\/jagm.2000.1130","volume":"38","author":"JD Oldham","year":"2001","unstructured":"Oldham JD (2001) Combinatorial approximation algorithms for generalized flow problems. J Algorithms 38(1):135\u2013169","journal-title":"J Algorithms"},{"issue":"2","key":"604_CR32","doi-asserted-by":"crossref","first-page":"257","DOI":"10.1287\/moor.20.2.257","volume":"20","author":"SA Plotkin","year":"1995","unstructured":"Plotkin SA, Shmoys DB, Tardos \u00c9 (1995) Fast approximation algorithms for fractional packing and covering problems. Math Oper Res 20(2):257\u2013301","journal-title":"Math Oper Res"},{"key":"604_CR33","volume-title":"Combinatorial optimization: polyhedra and efficiency","author":"A Schrijver","year":"2002","unstructured":"Schrijver A (2002) Combinatorial optimization: polyhedra and efficiency, vol 24. Springer, New York"},{"doi-asserted-by":"crossref","unstructured":"Toledo S (1992) Maximizing non-linear concave functions in fixed dimension. In: Proceedings 33rd annual symposium on foundations of computer science, 1992. pp 676\u2013685","key":"604_CR34","DOI":"10.1109\/SFCS.1992.267783"},{"issue":"1","key":"604_CR35","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/0020-0190(93)90149-4","volume":"47","author":"S Toledo","year":"1993","unstructured":"Toledo S (1993) Approximate parametric searching. Inf Process Lett 47(1):1\u20134","journal-title":"Inf Process Lett"},{"unstructured":"Wayne KD (1999) Generalized maximum flow algorithms. PhD thesis, Cornell University","key":"604_CR36"},{"issue":"3","key":"604_CR37","doi-asserted-by":"crossref","first-page":"445","DOI":"10.1287\/moor.27.3.445.313","volume":"27","author":"KD Wayne","year":"2002","unstructured":"Wayne KD (2002) A polynomial combinatorial algorithm for generalized minimum cost flow. Math Oper Res 27(3):445\u2013459","journal-title":"Math Oper Res"},{"key":"604_CR38","first-page":"170","volume":"95","author":"NE Young","year":"1995","unstructured":"Young NE (1995) Randomized rounding without solving the linear program. SODA 95:170\u2013178","journal-title":"SODA"}],"container-title":["Mathematical Methods of Operations Research"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00186-017-0604-2\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00186-017-0604-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00186-017-0604-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2018,1,23]],"date-time":"2018-01-23T13:27:46Z","timestamp":1516714066000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00186-017-0604-2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,7,28]]},"references-count":38,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2018,2]]}},"alternative-id":["604"],"URL":"https:\/\/doi.org\/10.1007\/s00186-017-0604-2","relation":{},"ISSN":["1432-2994","1432-5217"],"issn-type":[{"type":"print","value":"1432-2994"},{"type":"electronic","value":"1432-5217"}],"subject":[],"published":{"date-parts":[[2017,7,28]]}}}