{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,11,11]],"date-time":"2026-11-11T19:16:09Z","timestamp":1794424569450,"version":"4.9.1"},"publisher-location":"Berlin, Heidelberg","reference-count":22,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783642315930","type":"print"},{"value":"9783642315947","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2012]]},"DOI":"10.1007\/978-3-642-31594-7_51","type":"book-chapter","created":{"date-parts":[[2012,6,22]],"date-time":"2012-06-22T17:20:21Z","timestamp":1340385621000},"page":"606-616","source":"Crossref","is-referenced-by-count":5,"title":["A Rounding by Sampling Approach to the Minimum Size k-Arc Connected Subgraph Problem"],"prefix":"10.1007","author":[{"given":"Bundit","family":"Laekhanukit","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Shayan","family":"Oveis Gharan","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Mohit","family":"Singh","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","reference":[{"key":"51_CR1","doi-asserted-by":"crossref","unstructured":"Asadpour, A., Goemans, M.X., Madry, A., Gharan, S.O., Saberi, A.: An O(logn\/ loglogn)-approximation algorithm for the asymmetric traveling salesman problem. In: SODA, pp. 379\u2013389 (2010)","DOI":"10.1137\/1.9781611973075.32"},{"key":"51_CR2","unstructured":"An, H.-C., Kleinberg, R., Shmoys, D.B.: Improving Christofides\u2019 algorithm for the s-t path tsp. In: STOC (to appear, 2012)"},{"issue":"2","key":"51_CR3","doi-asserted-by":"crossref","first-page":"245","DOI":"10.1287\/moor.1060.0191","volume":"31","author":"M. Charikar","year":"2006","unstructured":"Charikar, M., Goemans, M.X., Karloff, H.J.: On the integrality ratio for the asymmetric traveling salesman problem. Math. Oper. Res.\u00a031(2), 245\u2013252 (2006); Preliminary version in FOCS 2004","journal-title":"Math. Oper. Res."},{"issue":"2","key":"51_CR4","doi-asserted-by":"crossref","first-page":"528","DOI":"10.1137\/S009753979833920X","volume":"30","author":"J. Cheriyan","year":"2000","unstructured":"Cheriyan, J., Thurimella, R.: Approximating minimum-size k-connected spanning subgraphs via matching. SIAM J. Comput.\u00a030(2), 528\u2013560 (2000); Preliminary version in FOCS 1996","journal-title":"SIAM J. Comput."},{"issue":"3","key":"51_CR5","doi-asserted-by":"publisher","first-page":"343","DOI":"10.1002\/rsa.10033","volume":"20","author":"R.D. Carr","year":"2002","unstructured":"Carr, R.D., Vempala, S.: Randomized metarounding. Random Struct. Algorithms\u00a020(3), 343\u2013352 (2002)","journal-title":"Random Struct. Algorithms"},{"key":"51_CR6","unstructured":"Edmonds, J.: Edge-disjoint branchings. In: Combinatorial algorithms (Courant Comput. Sci. Sympos. 9, New York Univ., New York, 1972), pp. 91\u201396. (1973)"},{"issue":"2","key":"51_CR7","doi-asserted-by":"publisher","first-page":"270","DOI":"10.1137\/0210019","volume":"10","author":"G.N. Frederickson","year":"1981","unstructured":"Frederickson, G.N., J\u00e1J\u00e1, J.: Approximation algorithms for several graph augmentation problems. SIAM J. Comput.\u00a010(2), 270\u2013283 (1981)","journal-title":"SIAM J. Comput."},{"key":"51_CR8","first-page":"77","volume":"41","author":"A. Frank","year":"1979","unstructured":"Frank, A.: Covering branchings. Acta Scientiarum Mathematicarum (Szeged)\u00a041, 77\u201381 (1979)","journal-title":"Acta Scientiarum Mathematicarum (Szeged)"},{"key":"51_CR9","doi-asserted-by":"crossref","unstructured":"Gabow, H.N.: A matroid approach to finding edge connectivity and packing arborescences. In: STOC, pp. 112\u2013122 (1991)","DOI":"10.1145\/103418.103436"},{"key":"51_CR10","unstructured":"Gabow, H.N.: Special edges, and approximating the smallest directed k-edge connected spanning subgraph. In: SODA, pp. 234\u2013243 (2004)"},{"key":"51_CR11","unstructured":"Gabow, H.N., Gallagher, S.: Iterated rounding algorithms for the smallest k-edge connected spanning subgraph. In: SODA, pp. 550\u2013559 (2008)"},{"issue":"4","key":"51_CR12","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\u00a053(4), 345\u2013357 (2009); Preliminary version in SODA 2005","journal-title":"Networks"},{"key":"51_CR13","doi-asserted-by":"publisher","first-page":"1138","DOI":"10.1287\/opre.18.6.1138","volume":"18","author":"M. Held","year":"1970","unstructured":"Held, M., Karp, R.: The traveling salesman problem and minimum spanning trees. Operations Research\u00a018, 1138\u20131162 (1970)","journal-title":"Operations Research"},{"issue":"1","key":"51_CR14","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\u00a021(1), 39\u201360 (2001); Preliminary version in FOCS 1998","journal-title":"Combinatorica"},{"key":"51_CR15","first-page":"177","volume-title":"Proceedings of the Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 1994","author":"S. Khuller","year":"1994","unstructured":"Khuller, S., Raghavachari, B., Young, N.E.: Approximating the minimum equivalent digraph. In: Proceedings of the Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 1994, pp. 177\u2013186. Society for Industrial and Applied Mathematics, Philadelphia (1994)"},{"issue":"3","key":"51_CR16","doi-asserted-by":"publisher","first-page":"281","DOI":"10.1016\/0166-218X(95)00105-Z","volume":"69","author":"S. Khuller","year":"1996","unstructured":"Khuller, S., Raghavachari, B., Young, N.E.: On strongly connected digraphs with bounded cycle length. Discrete Applied Mathematics\u00a069(3), 281\u2013289 (1996)","journal-title":"Discrete Applied Mathematics"},{"key":"51_CR17","doi-asserted-by":"crossref","unstructured":"Manshadi, V.H., Gharan, S.O., Saberi, A.: Online stochastic matching: Online actions based on offline statistics. In: SODA, pp. 1285\u20131294 (2011)","DOI":"10.1137\/1.9781611973082.98"},{"issue":"4","key":"51_CR18","doi-asserted-by":"publisher","first-page":"256","DOI":"10.1002\/net.20005","volume":"43","author":"V. Melkonian","year":"2004","unstructured":"Melkonian, V., Tardos, E.: Algorithms for a network design problem with crossing supermodular demands. Networks\u00a043(4), 256\u2013265 (2004)","journal-title":"Networks"},{"key":"51_CR19","doi-asserted-by":"crossref","unstructured":"Gharan, S.O., Saberi, A., Singh, M.: A randomized rounding approach to the traveling salesman problem. In: FOCS, pp. 550\u2013559 (2011)","DOI":"10.1109\/FOCS.2011.80"},{"key":"51_CR20","unstructured":"Schrijver, A.: Combinatorial Optimization. Springer (2003)"},{"key":"51_CR21","unstructured":"Vetta, A.: Approximating the minimum strongly connected subgraph via a matching lower bound. In: SODA, pp. 417\u2013426 (2001)"},{"key":"51_CR22","doi-asserted-by":"publisher","first-page":"63","DOI":"10.1016\/S0020-0190(02)00476-3","volume":"86","author":"L. Zhao","year":"2003","unstructured":"Zhao, L., Nagamochi, H., Ibaraki, T.: A linear time 5\/3-approximation for the minimum strongly-connected spanning subgraph problem. Inf. Process. Lett.\u00a086, 63\u201370 (2003)","journal-title":"Inf. Process. Lett."}],"container-title":["Lecture Notes in Computer Science","Automata, Languages, and Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-31594-7_51.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,5,4]],"date-time":"2021-05-04T08:15:09Z","timestamp":1620116109000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-31594-7_51"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012]]},"ISBN":["9783642315930","9783642315947"],"references-count":22,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-31594-7_51","relation":{"is-part-of":[{"id-type":"doi","id":"https:\/\/doi.org\/10.1007\/978-3-642-31594-7","asserted-by":"object"}]},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012]]}}}