{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,23]],"date-time":"2025-07-23T12:17:06Z","timestamp":1753273026341},"reference-count":37,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2012,10,23]],"date-time":"2012-10-23T00:00:00Z","timestamp":1350950400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2014,3]]},"DOI":"10.1007\/s00453-012-9701-z","type":"journal-article","created":{"date-parts":[[2012,10,22]],"date-time":"2012-10-22T15:32:44Z","timestamp":1350919964000},"page":"776-804","source":"Crossref","is-referenced-by-count":1,"title":["Multicommodity Flow in Trees: Packing via Covering and Iterated Relaxation"],"prefix":"10.1007","volume":"68","author":[{"given":"Jochen","family":"K\u00f6nemann","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ojas","family":"Parekh","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"David","family":"Pritchard","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2012,10,23]]},"reference":[{"key":"9701_CR1","doi-asserted-by":"crossref","first-page":"485","DOI":"10.1007\/s00493-010-2455-9","volume":"30","author":"M. Andrews","year":"2010","unstructured":"Andrews, M., Chuzhoy, J., Guruswami, V., Khanna, S., Talwar, K., Zhang, L.: Inapproximability of edge-disjoint paths and low congestion routing on undirected graphs. Combinatorica 30, 485\u2013520 (2010). doi: 10.1007\/s00493-010-2455-9","journal-title":"Combinatorica"},{"issue":"3","key":"9701_CR2","doi-asserted-by":"crossref","first-page":"153","DOI":"10.1016\/0020-0190(87)90178-5","volume":"24","author":"R.P. Anstee","year":"1987","unstructured":"Anstee, R.P.: A polynomial algorithm for b-matchings: an alternative approach. Inf. Process. Lett. 24(3), 153\u2013157 (1987). doi: 10.1016\/0020-0190(87)90178-5","journal-title":"Inf. Process. Lett."},{"issue":"4","key":"9701_CR3","doi-asserted-by":"crossref","first-page":"1413","DOI":"10.1137\/080734340","volume":"39","author":"N. Bansal","year":"2009","unstructured":"Bansal, N., Khandekar, R., Nagarajan, V.: Additive guarantees for degree-bounded directed network design. SIAM J. Comput. 39(4), 1413\u20131431 (2009). doi: 10.1137\/080734340 . Preliminary version In: Proc. 40th Symp. Theory Comp. (STOC), pp. 769\u2013778 (2008)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"9701_CR4","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/0166-218X(81)90022-6","volume":"3","author":"J. Beck","year":"1981","unstructured":"Beck, J., Fiala, T.: \u201cInteger-making\u201d theorems. Discrete Appl. Math. 3(1), 1\u20138 (1981). doi: 10.1016\/0166-218X(81)90022-6","journal-title":"Discrete Appl. Math."},{"key":"9701_CR5","first-page":"47","volume-title":"Proc. 52nd Symp. Found. Comp. Sci. (FOCS)","author":"P. Bonsma","year":"2011","unstructured":"Bonsma, P., Schulz, J., Wiese, A.: A constant factor approximation algorithm for unsplittable flow on paths. In: Proc. 52nd Symp. Found. Comp. Sci. (FOCS), pp. 47\u201356 (2011). doi: 10.1109\/FOCS.2011.10"},{"issue":"3","key":"9701_CR6","doi-asserted-by":"crossref","first-page":"221","DOI":"10.1007\/BF02592196","volume":"74","author":"A. Caprara","year":"1996","unstructured":"Caprara, A., Fischetti, M.: $\\{0,\\frac{1}{2} \\}$ -Chv\u00e1tal\u2013Gomory cuts. Math. Program. 74(3), 221\u2013235 (1996). doi: 10.1007\/BF02592196","journal-title":"Math. Program."},{"key":"9701_CR7","first-page":"355","volume-title":"Proc. 14th Conf. Int. Prog. Comb. Opt. (IPCO)","author":"D. Chakrabarty","year":"2010","unstructured":"Chakrabarty, D., Grant, E., K\u00f6nemann, J.: On column-restricted and priority covering integer programs. In: Proc. 14th Conf. Int. Prog. Comb. Opt. (IPCO), pp. 355\u2013368 (2010). doi: 10.1007\/978-3-642-13036-6_27"},{"key":"9701_CR8","first-page":"1576","volume-title":"Proc. 23rd Symp. Disc. Alg. (SODA)","author":"T.M. Chan","year":"2012","unstructured":"Chan, T.M., Grant, E., K\u00f6nemann, J., Sharpe, M.: Weighted capacitated, priority, and geometric set cover via improved quasi-uniform sampling. In: Proc. 23rd Symp. Disc. Alg. (SODA), pp. 1576\u20131585 (2012). http:\/\/dl.acm.org\/citation.cfm?id=2095116.2095241"},{"key":"9701_CR9","author":"C. Chekuri","year":"2007","unstructured":"Chekuri, C., Mydlarz, M., Shepherd, F.B.: Multicommodity demand flow in a tree and packing integer programs. ACM Trans. Algorithms (2007). doi: 10.1145\/1273340.1273343 . Preliminary version in Proc. 30th Int. Colloq. Automata, Lang. & Prog. (ICALP), pp. 410\u2013425 (2003)","journal-title":"ACM Trans. Algorithms"},{"key":"9701_CR10","first-page":"510","volume-title":"Proc. 7th European Symp. Alg. (ESA)","author":"J. Cheriyan","year":"1999","unstructured":"Cheriyan, J., Jord\u00e1n, T., Ravi, R.: On 2-coverings and 2-packings of laminar families. In: Proc. 7th European Symp. Alg. (ESA), pp. 510\u2013520 (1999). doi: 10.1007\/3-540-48481-7_44"},{"issue":"3","key":"9701_CR11","doi-asserted-by":"crossref","first-page":"320","DOI":"10.1016\/j.tcs.2005.11.029","volume":"354","author":"M. Chleb\u00edk","year":"2006","unstructured":"Chleb\u00edk, M., Chleb\u00edkov\u00e1, J.: Complexity of approximating bounded variants of optimization problems. Theor. Comput. Sci. 354(3), 320\u2013338 (2006). doi: 10.1016\/j.tcs.2005.11.029 . Preliminary version in Proc.\u00a014th Fund. Comp. Theory (FCT), pp. 27\u201338 (2003)","journal-title":"Theor. Comput. Sci."},{"key":"9701_CR12","first-page":"89","volume-title":"Combinatorial Structures and Their Applications (Proc. 1969 Calgary Conf. Comb. Struct. Appl.)","author":"J. Edmonds","year":"1970","unstructured":"Edmonds, J., Johnson, E.: Matching: A well-solved class of integer linear programs. In: Guy, R., Hanani, H., Sauer, N., Schonheim, J. (eds.) Combinatorial Structures and Their Applications (Proc. 1969 Calgary Conf. Comb. Struct. Appl.), pp. 89\u201392. Gordon and Breach, New York (1970)"},{"key":"9701_CR13","doi-asserted-by":"crossref","first-page":"97","DOI":"10.1007\/11671541_4","volume-title":"Efficient Approximation and Online Algorithms","author":"T. Erlebach","year":"2006","unstructured":"Erlebach, T.: Approximation algorithms for edge-disjoint paths and unsplittable flow. In: Bampis, E., Jansen, K., Kenyon, C. (eds.) Efficient Approximation and Online Algorithms, pp. 97\u2013134. Springer, Berlin (2006). Chap. 4, http:\/\/dl.acm.org\/citation.cfm?id=2168139.2168144"},{"key":"9701_CR14","doi-asserted-by":"crossref","unstructured":"Erlebach, T., Jansen, K.: Conversion of coloring algorithms into maximum weight independent set algorithms. Discrete Appl. Math. 148(1) (2005). doi: 10.1016\/j.dam.2004.11.007 . Preliminary version in Proc. Satellite Workshops 27th ICALP, pp. 135\u2013146 (2000)","DOI":"10.1016\/j.dam.2004.11.007"},{"key":"9701_CR15","doi-asserted-by":"crossref","first-page":"673","DOI":"10.1016\/j.dam.2005.05.017","volume":"154","author":"T. Erlebach","year":"2006","unstructured":"Erlebach, T., Vukadinovi\u0107, D.: Path problems in generalized stars, complete graphs, and brick wall graphs. Discrete Appl. Math. 154, 673\u2013683 (2006). doi: 10.1016\/j.dam.2005.05.017 . Preliminary version in Proc.\u00a013th Fund. Comp. Theory (FCT), pp. 483\u2013494 (2001)","journal-title":"Discrete Appl. Math."},{"issue":"4","key":"9701_CR16","doi-asserted-by":"crossref","first-page":"691","DOI":"10.1137\/0205048","volume":"5","author":"S. Even","year":"1976","unstructured":"Even, S., Itai, A., Shamir, A.: On the complexity of timetable and multicommodity flow problems. SIAM J. Comput. 5(4), 691\u2013703 (1976). doi: 10.1137\/0205048 . Preliminary version in Proc. 16th Symp. Found. Comp. Sci. (FOCS), pp. 184\u2013193 (1975)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"9701_CR17","doi-asserted-by":"crossref","first-page":"61","DOI":"10.1137\/080732572","volume":"41","author":"H.N. Gabow","year":"2012","unstructured":"Gabow, H.N., Gallagher, S.: Iterated rounding algorithms for the smallest k-edge connected spanning subgraph. SIAM J. Comput. 41(1), 61\u2013103 (2012). doi: 10.1137\/080732572 . Preliminary version in Proc. 19th Symp. Disc. Alg. (SODA), pp. 550\u2013559 (2008)","journal-title":"SIAM J. Comput."},{"issue":"4","key":"9701_CR18","doi-asserted-by":"crossref","first-page":"345","DOI":"10.1002\/net.20289","volume":"53","author":"H.N. Gabow","year":"2009","unstructured":"Gabow, H.N., Goemans, M.X., Tardos, \u00c9., Williamson, D.P.: Approximating the smallest k-edge connected spanning subgraph by LP-rounding. Networks 53(4), 345\u2013357 (2009). doi: 10.1002\/net.20289 . Preliminary version in Proc. 16th Symp. Disc. Alg. (SODA), pp. 562\u2013571 (2005)","journal-title":"Networks"},{"issue":"1","key":"9701_CR19","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1007\/BF02523685","volume":"18","author":"N. Garg","year":"1997","unstructured":"Garg, N., Vazirani, V.V., Yannakakis, M.: Primal-dual approximation algorithms for integral flow and multicut in trees. Algorithmica 18(1), 3\u201320 (1997). doi: 10.1007\/BF02523685 . Preliminary version in Proc. 20th Int. Colloq. Automata, Lang. & Prog. (ICALP), pp. 64\u201375 (1993)","journal-title":"Algorithmica"},{"key":"9701_CR20","first-page":"273","volume-title":"Proc. 47th Symp. Found. Comp. Sci. (FOCS)","author":"M.X. Goemans","year":"2006","unstructured":"Goemans, M.X.: Minimum bounded degree spanning trees. In: Proc. 47th Symp. Found. Comp. Sci. (FOCS), pp. 273\u2013282 (2006). doi: 10.1109\/FOCS.2006.48"},{"issue":"3","key":"9701_CR21","doi-asserted-by":"crossref","first-page":"473","DOI":"10.1016\/S0022-0000(03)00066-7","volume":"67","author":"V. Guruswami","year":"2003","unstructured":"Guruswami, V., Khanna, S., Rajaraman, R., Shepherd, F.B., Yannakakis, M.: Near-optimal hardness results and approximation algorithms for edge-disjoint paths and related problems. J. Comput. Syst. Sci. 67(3), 473\u2013496 (2003). Preliminary version in Proc. 31st Symp. Theory Comp. (STOC), pp. 19\u201328 (1999)","journal-title":"J. Comput. Syst. Sci."},{"key":"9701_CR22","doi-asserted-by":"crossref","first-page":"207","DOI":"10.1007\/BFb0035179","volume-title":"Proc. 4th Israel Symp. Theory Comput. & Systems","author":"I.B.-A. Hartman","year":"1992","unstructured":"Hartman, I.B.-A.: Optimal k-colouring and k-nesting of intervals. In: Proc. 4th Israel Symp. Theory Comput. & Systems, pp. 207\u2013220 (1992)"},{"issue":"1","key":"9701_CR23","doi-asserted-by":"crossref","first-page":"39","DOI":"10.1007\/s004930170004","volume":"21","author":"K. Jain","year":"2001","unstructured":"Jain, K.: A factor 2 approximation algorithm for the generalized Steiner network problem. Combinatorica 21(1), 39\u201360 (2001). doi: 10.1007\/s004930170004 . Preliminary version in Proc. 39th Symp. Found. Comp. Sci. (FOCS), pp. 448\u2013457 (1998)","journal-title":"Combinatorica"},{"key":"9701_CR24","unstructured":"Kann, V.: On the approximability of NP-complete optimization problems. PhD thesis, Royal Institute of Technology Stockholm (1992)"},{"key":"9701_CR25","doi-asserted-by":"crossref","first-page":"113","DOI":"10.1007\/BF01840353","volume":"2","author":"R.M. Karp","year":"1987","unstructured":"Karp, R.M., Leighton, F.T., Rivest, R.L., Thompson, C.D., Vazirani, U.V., Vazirani, V.V.: Global wire routing in two-dimensional arrays. Algorithmica 2, 113\u2013129 (1987). doi: 10.1007\/BF01840353","journal-title":"Algorithmica"},{"key":"9701_CR26","first-page":"1","volume-title":"Proc. 6th Int. Workshop Approx. & Online Alg. (WAOA)","author":"J. K\u00f6nemann","year":"2008","unstructured":"K\u00f6nemann, J., Parekh, O., Pritchard, D.: Max-weight integral multicommodity flow in spiders and high-capacity trees. In: Proc. 6th Int. Workshop Approx. & Online Alg. (WAOA), pp. 1\u201314 (2008). doi: 10.1007\/978-3-540-93980-1_1"},{"issue":"3","key":"9701_CR27","doi-asserted-by":"crossref","first-page":"1062","DOI":"10.1137\/070700620","volume":"39","author":"L. Lau","year":"2009","unstructured":"Lau, L., Naor, J., Salavatipour, M., Singh, M.: Survivable network design with degree or order constraints. SIAM J. Comput. 39(3), 1062\u20131087 (2009). doi: 10.1137\/070700620 . Preliminary version in Proc. 39th Symp. Theory Comp. (STOC), pp. 651\u2013660 (2007)","journal-title":"SIAM J. Comput."},{"issue":"3","key":"9701_CR28","doi-asserted-by":"crossref","first-page":"156","DOI":"10.1016\/j.orl.2010.02.005","volume":"38","author":"V. Nagarajan","year":"2010","unstructured":"Nagarajan, V., Ravi, R., Singh, M.: Simpler analysis of LP extreme points for traveling salesman and survivable network design problems. Oper. Res. Lett. 38(3), 156\u2013160 (2010). doi: 10.1016\/j.orl.2010.02.005","journal-title":"Oper. Res. Lett."},{"issue":"1","key":"9701_CR29","doi-asserted-by":"crossref","first-page":"10","DOI":"10.1016\/j.orl.2006.02.001","volume":"35","author":"T. Nguyen","year":"2007","unstructured":"Nguyen, T.: On the disjoint paths problem. Oper. Res. Lett. 35(1), 10\u201316 (2007). doi: 10.1016\/j.orl.2006.02.001","journal-title":"Oper. Res. Lett."},{"key":"9701_CR30","first-page":"349","volume-title":"Proc. 15th Conf. Int. Prog. Comb. Opt. (IPCO)","author":"O. Parekh","year":"2011","unstructured":"Parekh, O.: Iterative packing for demand and hypergraph matching. In: Proc. 15th Conf. Int. Prog. Comb. Opt. (IPCO), pp. 349\u2013361 (2011). doi: 10.1007\/978-3-642-20807-2_28"},{"key":"9701_CR31","doi-asserted-by":"crossref","first-page":"213","DOI":"10.1007\/978-3-642-18318-8_19","volume-title":"Proc. 8th WAOA (Workshop Approx. & Online Alg.)","author":"B. Peis","year":"2011","unstructured":"Peis, B., Wiese, A.: Throughput maximization for periodic packet routing on trees and grids. In: Proc. 8th WAOA (Workshop Approx. & Online Alg.), pp. 213\u2013224 (2011). doi: 10.1007\/978-3-642-18318-8_19"},{"key":"9701_CR32","first-page":"225","volume-title":"Proc. 8th WAOA (Workshop Approx. & Online Alg.)","author":"D. Pritchard","year":"2010","unstructured":"Pritchard, D.: k-edge-connectivity: approximation and LP relaxation. In: Proc. 8th WAOA (Workshop Approx. & Online Alg.), pp. 225\u2013236 (2010). doi: 10.1007\/978-3-642-18318-8_20"},{"issue":"1","key":"9701_CR33","doi-asserted-by":"crossref","first-page":"75","DOI":"10.1007\/s00453-010-9431-z","volume":"61","author":"D. Pritchard","year":"2011","unstructured":"Pritchard, D., Chakrabarty, D.: Approximability of sparse integer programs. Algorithmica 61(1), 75\u201393 (2011). doi: 10.1007\/s00453-010-9431-z . Preliminary version in Proc. 17th European Symp. Alg. (ESA), pp. 83\u201394 (2009)","journal-title":"Algorithmica"},{"key":"9701_CR34","doi-asserted-by":"crossref","first-page":"365","DOI":"10.1007\/BF02579324","volume":"7","author":"P. Raghavan","year":"1987","unstructured":"Raghavan, P., Thompson, C.: Randomized rounding: a technique for provably good algorithms and algorithmic proofs. Combinatorica 7, 365\u2013374 (1987). doi: 10.1007\/BF02579324","journal-title":"Combinatorica"},{"key":"9701_CR35","isbn-type":"print","volume-title":"Combinatorial Optimization: Polyhedra and Efficiency","author":"A. Schrijver","year":"2003","unstructured":"Schrijver, A.: Combinatorial Optimization: Polyhedra and Efficiency. Springer, Berlin (2003). 3-540-44389-4","ISBN":"http:\/\/id.crossref.org\/isbn\/3540443894"},{"issue":"3","key":"9701_CR36","doi-asserted-by":"crossref","first-page":"563","DOI":"10.1287\/moor.1070.0254","volume":"32","author":"F.B. Shepherd","year":"2007","unstructured":"Shepherd, F.B., Vetta, A.: The demand-matching problem. Math. Oper. Res. 32(3), 563\u2013578 (2007). doi: 10.1287\/moor.1070.0254 . Preliminary version in Proc. 9th Conf. Int. Prog. Comb. Opt. (IPCO), pp. 457\u2013474 (2002)","journal-title":"Math. Oper. Res."},{"key":"9701_CR37","first-page":"661","volume-title":"Proc. 39th Symp. Theory Comp. (STOC)","author":"M. Singh","year":"2007","unstructured":"Singh, M., Lau, L.C.: Approximating minimum bounded degree spanning trees to within one of optimal. In: Proc. 39th Symp. Theory Comp. (STOC), pp. 661\u2013670 (2007). doi: 10.1145\/1250790.1250887"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-012-9701-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-012-9701-z\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-012-9701-z","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,29]],"date-time":"2019-05-29T13:45:10Z","timestamp":1559137510000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-012-9701-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,10,23]]},"references-count":37,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2014,3]]}},"alternative-id":["9701"],"URL":"https:\/\/doi.org\/10.1007\/s00453-012-9701-z","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012,10,23]]}}}