{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,9]],"date-time":"2025-10-09T13:09:11Z","timestamp":1760015351781},"publisher-location":"Berlin, Heidelberg","reference-count":14,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540755197"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/978-3-540-75520-3_36","type":"book-chapter","created":{"date-parts":[[2007,9,14]],"date-time":"2007-09-14T03:46:33Z","timestamp":1189741593000},"page":"395-406","source":"Crossref","is-referenced-by-count":5,"title":["Convex Combinations of Single Source Unsplittable Flows"],"prefix":"10.1007","author":[{"given":"Maren","family":"Martens","sequence":"first","affiliation":[]},{"given":"Fernanda","family":"Salazar","sequence":"additional","affiliation":[]},{"given":"Martin","family":"Skutella","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"36_CR1","first-page":"284","volume-title":"Proceedings of 37th Annual ACM Symposium on Theory of Computing","author":"M. Andrews","year":"2005","unstructured":"Andrews, M., Zhang, L.: Hardness of the undirected congestion minimization problem. In: Proceedings of 37th Annual ACM Symposium on Theory of Computing, pp. 284\u2013293. ACM Press, New York (2005)"},{"key":"36_CR2","doi-asserted-by":"crossref","unstructured":"Azar, Y., Regev, O.: Strongly polynomial algorithms for the unsplittable flow problem. In: Proceedings of the 8th Conference on Integer Programming and Combinatorial Optimization, pp. 15\u201329 (2001)","DOI":"10.1007\/3-540-45535-3_2"},{"key":"36_CR3","first-page":"28","volume-title":"Proceedings of the 36th Annual ACM Symposium on Theory of Computing","author":"J. Chuzhoy","year":"2004","unstructured":"Chuzhoy, J., Naor, J.: New hardness results for congestion minimization and machine scheduling. In: Proceedings of the 36th Annual ACM Symposium on Theory of Computing, pp. 28\u201334. ACM Press, New York (2004)"},{"key":"36_CR4","doi-asserted-by":"publisher","first-page":"17","DOI":"10.1007\/s004930050043","volume":"19","author":"Y. Dinitz","year":"1999","unstructured":"Dinitz, Y., Garg, N., Goemans, M.X.: On the single source unsplittable flow problem. Combinatorica\u00a019, 17\u201341 (1999)","journal-title":"Combinatorica"},{"key":"36_CR5","doi-asserted-by":"publisher","first-page":"2","DOI":"10.1145\/1064546.1180614","volume":"10","author":"J. Du","year":"2005","unstructured":"Du, J., Kolliopoulos, S.: Implementing approximation algorithms for the single-source unsplittable flow problem. Journal of Experimental Algorithmics\u00a010, 2\u20133 (2005)","journal-title":"Journal of Experimental Algorithmics"},{"key":"36_CR6","unstructured":"Goemans, M.X.: Cited as personal communication from (January 2000) [14, Section\u00a07]"},{"key":"36_CR7","first-page":"19","volume-title":"Proceedings of the 31st Annual ACM Symposium on Theory of Computing","author":"V. Guruswami","year":"1999","unstructured":"Guruswami, V., Khanna, S., Rajaraman, R., Shepherd, B., Yannakakis, M.: Near-optimal hardness results and approximation algorithms for edge-disjoint paths and related problems. In: Proceedings of the 31st Annual ACM Symposium on Theory of Computing, pp. 19\u201328. ACM Press, New York (1999)"},{"key":"36_CR8","unstructured":"Kleinberg, J.M.: Approximation Algorithms for Disjoint Path Problems. PhD thesis, Massachusetts Institute of Technology (May 1996)"},{"key":"36_CR9","doi-asserted-by":"publisher","first-page":"919","DOI":"10.1137\/S0097539799355314","volume":"31","author":"S.G. Kolliopoulos","year":"2002","unstructured":"Kolliopoulos, S.G., Stein, C.: Approximation algorithms for single-source unsplittable flow. SIAM Journal on Computing\u00a031, 919\u2013946 (2002)","journal-title":"SIAM Journal on Computing"},{"key":"36_CR10","first-page":"184","volume-title":"Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms","author":"P. Kolman","year":"2002","unstructured":"Kolman, P., Scheideler, C.: Improved bounds for the unsplittable flow problem. In: Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 184\u2013193. ACM Press, New York (2002)"},{"key":"36_CR11","doi-asserted-by":"publisher","first-page":"259","DOI":"10.1007\/BF01585745","volume":"46","author":"J.K. Lenstra","year":"1990","unstructured":"Lenstra, J.K., Shmoys, D.B., Tardos, \u00c9.: Approximation algorithms for scheduling unrelated parallel machines. Mathematical Programming\u00a046, 259\u2013271 (1990)","journal-title":"Mathematical Programming"},{"key":"36_CR12","doi-asserted-by":"publisher","first-page":"130","DOI":"10.1016\/0022-0000(88)90003-7","volume":"37","author":"P. Raghavan","year":"1988","unstructured":"Raghavan, P.: Probabilistic construction of deterministic algorithms: approximating packing integer programs. Journal of Computer and System Sciences\u00a037, 130\u2013143 (1988)","journal-title":"Journal of Computer and System Sciences"},{"key":"36_CR13","doi-asserted-by":"publisher","first-page":"365","DOI":"10.1007\/BF02579324","volume":"7","author":"P. Raghavan","year":"1987","unstructured":"Raghavan, P., Thompson, C.D.: Randomized rounding: A technique for provably good algorithms and algorithmic proofs. Combinatorica\u00a07, 365\u2013374 (1987)","journal-title":"Combinatorica"},{"key":"36_CR14","doi-asserted-by":"publisher","first-page":"493","DOI":"10.1007\/s101070100260","volume":"91","author":"M. Skutella","year":"2002","unstructured":"Skutella, M.: Approximating the single source unsplittable min-cost flow problem. Mathematical Programming\u00a091, 493\u2013514 (2002)","journal-title":"Mathematical Programming"}],"container-title":["Lecture Notes in Computer Science","Algorithms \u2013 ESA 2007"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-75520-3_36.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T10:22:53Z","timestamp":1619518973000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-75520-3_36"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["9783540755197"],"references-count":14,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-75520-3_36","relation":{},"subject":[]}}