{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,10]],"date-time":"2026-06-10T07:52:50Z","timestamp":1781077970269,"version":"3.54.1"},"publisher-location":"Cham","reference-count":13,"publisher":"Springer International Publishing","isbn-type":[{"value":"9783319075563","type":"print"},{"value":"9783319075570","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2014]]},"DOI":"10.1007\/978-3-319-07557-0_24","type":"book-chapter","created":{"date-parts":[[2014,5,17]],"date-time":"2014-05-17T11:50:30Z","timestamp":1400327430000},"page":"285-296","source":"Crossref","is-referenced-by-count":9,"title":["Linear Programming Hierarchies Suffice for Directed Steiner Tree"],"prefix":"10.1007","author":[{"given":"Zachary","family":"Friggstad","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jochen","family":"K\u00f6nemann","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Young","family":"Kun-Ko","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Anand","family":"Louis","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Mohammad","family":"Shadravan","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Madhur","family":"Tulsiani","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","reference":[{"issue":"3","key":"24_CR1","doi-asserted-by":"publisher","first-page":"281","DOI":"10.1007\/s10878-005-1412-9","volume":"9","author":"G. Calinescu","year":"2005","unstructured":"Calinescu, G., Zelikovsky, G.: The polymatroid Steiner problems. J. Combinatorial Optimization\u00a09(3), 281\u2013294 (2005)","journal-title":"J. Combinatorial Optimization"},{"issue":"1","key":"24_CR2","doi-asserted-by":"publisher","first-page":"73","DOI":"10.1006\/jagm.1999.1042","volume":"33","author":"M. Charikar","year":"1999","unstructured":"Charikar, M., Chekuri, C., Cheung, T., Dai, Z., Goel, A., Guha, S., Li, M.: Approximation algorithms for directed Steiner problems. J. Algorithms\u00a033(1), 73\u201391 (1999)","journal-title":"J. Algorithms"},{"key":"24_CR3","doi-asserted-by":"crossref","unstructured":"Chlamt\u00e1\u010d, E., Tulsiani, M.: Convex relaxations and integrality gaps. In: Handbook on Semidefinite. Springer (2012)","DOI":"10.1007\/978-1-4614-0769-0_6"},{"issue":"1","key":"24_CR4","doi-asserted-by":"publisher","first-page":"66","DOI":"10.1006\/jagm.2000.1096","volume":"37","author":"N. Garg","year":"2000","unstructured":"Garg, N., Konjevod, G., Ravi, R.: A polylogarithmic approximation algorithm for the group Steiner tree problem. J. Algorithms\u00a037(1), 66\u201384 (2000)","journal-title":"J. Algorithms"},{"key":"24_CR5","doi-asserted-by":"crossref","unstructured":"Gupta, A., Talwar, K., Witmer, D.: Sparsest cut on bounded treewidth graphs: algorithms and hardness results. In: Proceedings of STOC (2013)","DOI":"10.1145\/2488608.2488644"},{"key":"24_CR6","doi-asserted-by":"crossref","unstructured":"Guruswami, V., Sinop, A.K.: Faster SDP hierarchy solvers for local rounding algorithms. In: Proceedings of FOCS (2012)","DOI":"10.1109\/FOCS.2012.58"},{"key":"24_CR7","doi-asserted-by":"crossref","unstructured":"Halperin, E., Krauthgamer, R.: Polylogarithmic inapproximability. In: Proceedings of STOC (2003)","DOI":"10.1145\/780627.780628"},{"key":"24_CR8","doi-asserted-by":"crossref","unstructured":"Karlin, A., Mathieu, C., Nguyen, C.: Integrlaity gaps of linear and semidefinite programming relaxations for knapsack. In: Proceedings of IPCO (2011)","DOI":"10.1007\/978-3-642-20807-2_24"},{"key":"24_CR9","unstructured":"Rothvoss, T.: Directed Steiner tree and the Lasserre hierarchy. CoRR abs\/1111.5473 (2011)"},{"key":"24_CR10","doi-asserted-by":"publisher","first-page":"411","DOI":"10.1137\/0403036","volume":"3","author":"H. Sherali","year":"1990","unstructured":"Sherali, H., Adams, W.: A hierarchy of relaxations between the continuous and convex hull representations for zero-one programming problems. SIAM J. Discrete Math.\u00a03, 411\u2013430 (1990)","journal-title":"SIAM J. Discrete Math."},{"key":"24_CR11","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1007\/BF02523690","volume":"18","author":"A. Zelikovsky","year":"1997","unstructured":"Zelikovsky, A.: A series of approximation algorithms for the acyclic directed Steiner tree problem. Algorithmica\u00a018, 99\u2013110 (1997)","journal-title":"Algorithmica"},{"key":"24_CR12","unstructured":"Zosin, L., Khuller, S.: On directed Steiner trees. In: Proceedings of SODA (2002)"},{"key":"24_CR13","doi-asserted-by":"publisher","first-page":"166","DOI":"10.1137\/0801013","volume":"1","author":"L. Lov\u00e1sz","year":"1991","unstructured":"Lov\u00e1sz, L., Schrijver, A.: Cones of matrices and set-functions and 0-1 optimization. SIAM Journal on Optimization\u00a01, 166\u2013190 (1991)","journal-title":"SIAM Journal on Optimization"}],"container-title":["Lecture Notes in Computer Science","Integer Programming and Combinatorial Optimization"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-07557-0_24","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,26]],"date-time":"2019-05-26T21:19:23Z","timestamp":1558905563000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-07557-0_24"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014]]},"ISBN":["9783319075563","9783319075570"],"references-count":13,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-07557-0_24","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014]]}}}