{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T00:47:30Z","timestamp":1725497250919},"publisher-location":"Berlin, Heidelberg","reference-count":19,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540771180"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/978-3-540-77120-3_28","type":"book-chapter","created":{"date-parts":[[2007,12,6]],"date-time":"2007-12-06T11:31:09Z","timestamp":1196940669000},"page":"304-315","source":"Crossref","is-referenced-by-count":7,"title":["Approximability of Packing Disjoint Cycles"],"prefix":"10.1007","author":[{"given":"Zachary","family":"Friggstad","sequence":"first","affiliation":[]},{"given":"Mohammad R.","family":"Salavatipour","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"28_CR1","doi-asserted-by":"crossref","unstructured":"Andrews, M., Chuzhoy, J., Khanna, S., Zhang, L.: Hardness of the undirected edge-disjoint paths problem with congestion. In: Proc. of 46th IEEE FOCS, pp. 226\u2013244 (2005)","DOI":"10.1109\/SFCS.2005.41"},{"key":"28_CR2","first-page":"276","volume-title":"Proc. of 37th ACM STOC","author":"M. Andrews","year":"2005","unstructured":"Andrews, M., Zhang, L.: Hardness of the undirected edge-disjoint paths problem. In: Proc. of 37th ACM STOC, pp. 276\u2013283. ACM Press, New York (2005)"},{"key":"28_CR3","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1017\/S0963548302005461","volume":"12","author":"P. Balister","year":"2003","unstructured":"Balister, P.: Packing digraphs with directed closed trials. Combin. Probab. Comput.\u00a012, 1\u201315 (2003)","journal-title":"Combin. Probab. Comput."},{"key":"28_CR4","first-page":"1","volume":"44","author":"A. Caprara","year":"1999","unstructured":"Caprara, A., Panconesi, A., Rizzi, R.: Packing cuts in undirected graphs. J. Algorithms\u00a044, 1\u201311 (1999)","journal-title":"J. Algorithms"},{"key":"28_CR5","doi-asserted-by":"publisher","first-page":"239","DOI":"10.1016\/S0196-6774(03)00052-X","volume":"48","author":"A. Caprara","year":"2003","unstructured":"Caprara, A., Panconesi, A., Rizzi, R.: Packing cycles in undirected graphs. J. Algorithms\u00a048, 239\u2013256 (2003)","journal-title":"J. Algorithms"},{"key":"28_CR6","unstructured":"Chekuri, C., Khanna, S.: Edge disjoint paths revisited. In: Proc. of 14th ACM-SIAM SODA, pp. 628\u2013637 (2003)"},{"key":"28_CR7","doi-asserted-by":"publisher","first-page":"137","DOI":"10.4086\/toc.2006.v002a007","volume":"2","author":"C. Chekuri","year":"2006","unstructured":"Chekuri, C., Khanna, S., Shepherd, B.: An \n                    \n                      \n                    \n                    $O(\\sqrt{n})$\n                   Approximation and Integrality Gap for Disjoint Paths and UFP. Theory of Computing\u00a02, 137\u2013146 (2006)","journal-title":"Theory of Computing"},{"issue":"4","key":"28_CR8","doi-asserted-by":"publisher","first-page":"538","DOI":"10.1145\/1082036.1082038","volume":"52","author":"J. Chuzhoy","year":"2005","unstructured":"Chuzhoy, J., Guha, S., Halperin, E., Khanna, S., Kortsarz, G., Krauthgamer, R., Naor, S.: Tight lower bounds for the asymmetric k-center problem. Journal of ACM\u00a052(4), 538\u2013551 (2005)","journal-title":"Journal of ACM"},{"key":"28_CR9","unstructured":"Chuzhoy, J., Khanna, S.: New hardness results for undirected edge disjoint paths, Manuscript (2005)"},{"key":"28_CR10","first-page":"252","volume-title":"Proc. of 20th ACM STOC","author":"D. Dor","year":"1992","unstructured":"Dor, D., Tarsi, M.: Graph decomposition is NPC \u2013 A complete proof of Holyer\u2019s conjecture. In: Proc. of 20th ACM STOC, pp. 252\u2013263. ACM Press, New York (1992)"},{"issue":"3","key":"28_CR11","doi-asserted-by":"publisher","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, B., Yannakakis, M.: Near-Optimal Hardness Results and Approximation Algorithms for Edge-Disjoint Paths and Related Problems. J. of Computer and System Sciences\u00a067(3), 473\u2013496 (2003) Earlier version in STOC 1999.","journal-title":"J. of Computer and System Sciences"},{"key":"28_CR12","doi-asserted-by":"crossref","unstructured":"Halldorsson, M.M., Kortsarz, G., Radhakrishnan, J., Sivasubramanian, S.: Complete Partitions of Graphs. Combinatorica (to appear)","DOI":"10.1007\/s00493-007-2169-9"},{"key":"28_CR13","unstructured":"Kleinberg, J.: Approximation algorithms for disjoint paths problems, PhD. Thesis, MIT, Cambridge, MA (May 1996)"},{"key":"28_CR14","unstructured":"Krivelevich, M., Nutov, Z., Yuster, R.: Approximation algorithms for cycle packing problems. In: Proc. of 16th ACM-SIAM SODA, pp. 556\u2013561 (2005)"},{"key":"28_CR15","doi-asserted-by":"crossref","unstructured":"Krivelevich, M., Nutov, Z., Salavatipour, M.R., Verstraete, J., Yuster, R.: Approximation Algorithms and Hardness Results for Cycle Packing Problems. ACM Transactions on Algorithms (to appear)","DOI":"10.1145\/1290672.1290685"},{"key":"28_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"51","DOI":"10.1007\/11496915_5","volume-title":"Integer Programming and Combinatorial Optimization","author":"M.R. Salavatipour","year":"2005","unstructured":"Salavatipour, M.R., Verstraete, J.: Disjoint cycles: Integrality gap, hardness, and approximation. In: J\u00fcnger, M., Kaibel, V. (eds.) Integer Programming and Combinatorial Optimization. LNCS, vol.\u00a03509, pp. 51\u201365. Springer, Heidelberg (2005)"},{"key":"28_CR17","first-page":"191","volume-title":"Proc. of 32nd ACM STOC","author":"A. Samorodnitsky","year":"2000","unstructured":"Samorodnitsky, A., Trevisan, L.: A PCP characterization of NP with optimal amortized query complexity. In: Proc. of 32nd ACM STOC, pp. 191\u2013199. ACM Press, New York (2000)"},{"key":"28_CR18","doi-asserted-by":"publisher","first-page":"281","DOI":"10.1007\/BF01200760","volume":"15","author":"P.D. Seymour","year":"1995","unstructured":"Seymour, P.D.: Packing directed circuits fractionally. Combinatorica\u00a015, 281\u2013288 (1995)","journal-title":"Combinatorica"},{"key":"28_CR19","unstructured":"Varadarajan, K.R., Venkataraman, G.: Graph decomposition and a greedy algorithm for edge-disjoint paths. In: Proc. of 15 ACM-SIAM SODA, pp. 379\u2013380 (2004)"}],"container-title":["Lecture Notes in Computer Science","Algorithms and Computation"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-77120-3_28.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T11:01:09Z","timestamp":1619521269000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-77120-3_28"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["9783540771180"],"references-count":19,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-77120-3_28","relation":{},"subject":[]}}