{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,27]],"date-time":"2026-03-27T14:07:17Z","timestamp":1774620437162,"version":"3.50.1"},"reference-count":24,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2007,8,1]],"date-time":"2007-08-01T00:00:00Z","timestamp":1185926400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2007,8]]},"abstract":"<jats:p>\n            We consider requests for capacity in a given tree network\n            <jats:italic>T<\/jats:italic>\n            = (\n            <jats:italic>V<\/jats:italic>\n            ,\n            <jats:italic>E<\/jats:italic>\n            ) where each edge\n            <jats:italic>e<\/jats:italic>\n            of the tree has some integer capacity\n            <jats:italic>u<\/jats:italic>\n            <jats:sub>e<\/jats:sub>\n            . Each request\n            <jats:italic>f<\/jats:italic>\n            is a node pair with an integer demand\n            <jats:italic>d<\/jats:italic>\n            <jats:sub>f<\/jats:sub>\n            and a profit\n            <jats:italic>w<\/jats:italic>\n            <jats:sub>f<\/jats:sub>\n            which is obtained if the request is satisfied. The objective is to find a set of demands that can be feasibly routed in the tree and which provides a maximum profit. This generalizes well-known problems, including the knapsack and\n            <jats:italic>b<\/jats:italic>\n            -matching problems.\n          <\/jats:p>\n          <jats:p>When all demands are 1, we have the integer multicommodity flow problem. Garg et al. [1997] had shown that this problem is NP-hard and gave a 2-approximation algorithm for the cardinality case (all profits are 1) via a primal-dual algorithm. Our main result establishes that the integrality gap of the natural linear programming relaxation is at most 4 for the case of arbitrary profits. Our proof is based on coloring paths on trees and this has other applications for wavelength assignment in optical network routing.<\/jats:p>\n          <jats:p>\n            We then consider the problem with arbitrary demands. When the maximum demand\n            <jats:italic>d<\/jats:italic>\n            <jats:sub>max<\/jats:sub>\n            is at most the minimum edge capacity\n            <jats:italic>u<\/jats:italic>\n            <jats:sub>min<\/jats:sub>\n            , we show that the integrality gap of the LP is at most 48. This result is obtained by showing that the integrality gap for the demand version of such a problem is at most 11.542 times that for the unit-demand case. We use techniques of Kolliopoulos and Stein [2004, 2001] to obtain this. We also obtain, via this method, improved algorithms for line and ring networks. Applications and connections to other combinatorial problems are discussed.\n          <\/jats:p>","DOI":"10.1145\/1273340.1273343","type":"journal-article","created":{"date-parts":[[2007,9,14]],"date-time":"2007-09-14T13:44:55Z","timestamp":1189777495000},"page":"27","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":73,"title":["Multicommodity demand flow in a tree and packing integer programs"],"prefix":"10.1145","volume":"3","author":[{"given":"Chandra","family":"Chekuri","sequence":"first","affiliation":[{"name":"University of Illinois, Urbana, IL"}]},{"given":"Marcelo","family":"Mydlarz","sequence":"additional","affiliation":[{"name":"Yahoo! Research, Santiago, Chile"}]},{"given":"F. Bruce","family":"Shepherd","sequence":"additional","affiliation":[{"name":"McGill University, Montreal, Quebec, Canada"}]}],"member":"320","published-online":{"date-parts":[[2007,8]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.2005.41"},{"key":"e_1_2_1_2_1","volume-title":"Proceedings of the Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM). 409--419","author":"Andrews M.","unstructured":"Andrews , M. , and Zhang , L . 2005a. Bounds on fiber minimization in optical networks with fixed fiber capacity . In Proceedings of the Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM). 409--419 . Andrews, M., and Zhang, L. 2005a. Bounds on fiber minimization in optical networks with fixed fiber capacity. In Proceedings of the Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM). 409--419."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/1060590.1060632"},{"key":"e_1_2_1_4_1","volume-title":"Proceedings of the Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM).","author":"Andrews M.","unstructured":"Andrews , M. , and Zhang , L . 2006. Complexity of wavelength assignment in optical network optimization . In Proceedings of the Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM). Andrews, M., and Zhang, L. 2006. Complexity of wavelength assignment in optical network optimization. In Proceedings of the Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM)."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/1132516.1132617"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/502102.502107"},{"key":"e_1_2_1_7_1","series-title":"Lecture Notes in Economics and Mathematics Systems","volume-title":"Integer rounding and polyhedral decomposition for totally unimodular systems","author":"Baum S.","unstructured":"Baum , S. , and Trotter Jr ., L. E. 1978. Integer rounding and polyhedral decomposition for totally unimodular systems . In Optimization and Operations Research, R. Henn et al. eds. Lecture Notes in Economics and Mathematics Systems , vol. 157 . Springer , 15--23. Baum, S., and Trotter Jr., L. E. 1978. Integer rounding and polyhedral decomposition for totally unimodular systems. In Optimization and Operations Research, R. Henn et al. eds. Lecture Notes in Economics and Mathematics Systems, vol. 157. Springer, 15--23."},{"key":"e_1_2_1_8_1","volume-title":"Proceedings of the 9th International Conference on Integer Programming and Combinatorial Optimization (IPCO). Lecture Notes in Computer Science","volume":"2337","author":"Calinescu G.","unstructured":"Calinescu , G. , Chakrabarti , A. , Karloff , H. J. , and Rabani , Y . 2002. Improved approximation algorithms for resource allocation . In Proceedings of the 9th International Conference on Integer Programming and Combinatorial Optimization (IPCO). Lecture Notes in Computer Science , vol. 2337 . Springer, 401--414. Calinescu, G., Chakrabarti, A., Karloff, H. J., and Rabani, Y. 2002. Improved approximation algorithms for resource allocation. In Proceedings of the 9th International Conference on Integer Programming and Combinatorial Optimization (IPCO). Lecture Notes in Computer Science, vol. 2337. Springer, 401--414."},{"key":"e_1_2_1_9_1","volume-title":"Proceedings of the 5th International Workshop on Approximation Algorithms for Combinatorial Optimization (APPROX). 51--66","author":"Chakrabarti A.","unstructured":"Chakrabarti , A. , Chekuri , C. , Gupta , A. , and Kumar , A . 2002. Approximation algorithms for the unsplittable flow problem . In Proceedings of the 5th International Workshop on Approximation Algorithms for Combinatorial Optimization (APPROX). 51--66 . Chakrabarti, A., Chekuri, C., Gupta, A., and Kumar, A. 2002. Approximation algorithms for the unsplittable flow problem. In Proceedings of the 5th International Workshop on Approximation Algorithms for Combinatorial Optimization (APPROX). 51--66."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/1132516.1132621"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2006.v002a007"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/1007352.1007383"},{"key":"e_1_2_1_13_1","volume-title":"Proceedings of the 7th Annual European Symposium on Algorithms (ESA). 510--520","author":"Cheriyan J.","unstructured":"Cheriyan , J. , Jord\u00e1n , T. , and Ravi , R . 1999. On 2-coverings and 2-packings of laminar families . In Proceedings of the 7th Annual European Symposium on Algorithms (ESA). 510--520 . Cheriyan, J., Jord\u00e1n, T., and Ravi, R. 1999. On 2-coverings and 2-packings of laminar families. In Proceedings of the 7th Annual European Symposium on Algorithms (ESA). 510--520."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/s004930050043"},{"key":"e_1_2_1_15_1","volume-title":"Proceedings of the 29th International Workshop on Graph-Theoretic Concepts in Computer Science (WG). 218--229","author":"Erlebach T.","unstructured":"Erlebach , T. , Pagourtzis , A. , Potika , K. , and Stefanakos , S . 2003. Resource allocation problems in multifiber wdm tree networks . In Proceedings of the 29th International Workshop on Graph-Theoretic Concepts in Computer Science (WG). 218--229 . Erlebach, T., Pagourtzis, A., Potika, K., and Stefanakos, S. 2003. Resource allocation problems in multifiber wdm tree networks. In Proceedings of the 29th International Workshop on Graph-Theoretic Concepts in Computer Science (WG). 218--229."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02523685"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(03)00066-7"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-002-0370-6"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539799355314"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/195058.195119"},{"key":"e_1_2_1_22_1","volume-title":"Theory of Linear and Integer Programming","author":"Schrijver A.","unstructured":"Schrijver , A. 1986. Theory of Linear and Integer Programming . John Wiley & amp; Sons. Schrijver, A. 1986. Theory of Linear and Integer Programming. John Wiley &amp; Sons."},{"key":"e_1_2_1_23_1","doi-asserted-by":"crossref","unstructured":"Shepherd F. B. and Vetta A. 2007. The demand matching problem. Math. Oper. Res. To appear. Preliminary version in Proceedings of the International Conference on Integer Programming and Combinatorial Optimization (IPCO) 2002.   Shepherd F. B. and Vetta A. 2007. The demand matching problem. Math. Oper. Res. To appear. Preliminary version in Proceedings of the International Conference on Integer Programming and Combinatorial Optimization (IPCO) 2002.","DOI":"10.1007\/3-540-47867-1_32"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0166-218X(00)00252-3"},{"key":"e_1_2_1_25_1","unstructured":"Wolsey L. 2002. Private communication.  Wolsey L. 2002. Private communication."}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1273340.1273343","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1273340.1273343","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T14:57:55Z","timestamp":1750258675000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1273340.1273343"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007,8]]},"references-count":24,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2007,8]]}},"alternative-id":["10.1145\/1273340.1273343"],"URL":"https:\/\/doi.org\/10.1145\/1273340.1273343","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"value":"1549-6325","type":"print"},{"value":"1549-6333","type":"electronic"}],"subject":[],"published":{"date-parts":[[2007,8]]},"assertion":[{"value":"2007-08-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}