{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,23]],"date-time":"2026-07-23T01:39:50Z","timestamp":1784770790163,"version":"3.55.0"},"publisher-location":"Berlin, Heidelberg","reference-count":20,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783642229343","type":"print"},{"value":"9783642229350","type":"electronic"}],"license":[{"start":{"date-parts":[[2011,1,1]],"date-time":"2011-01-01T00:00:00Z","timestamp":1293840000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2011]]},"DOI":"10.1007\/978-3-642-22935-0_7","type":"book-chapter","created":{"date-parts":[[2011,8,12]],"date-time":"2011-08-12T05:20:39Z","timestamp":1313126439000},"page":"75-86","source":"Crossref","is-referenced-by-count":7,"title":["Optimal Lower Bounds for Universal and Differentially Private Steiner Trees and TSPs"],"prefix":"10.1007","author":[{"given":"Anand","family":"Bhalgat","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Deeparnab","family":"Chakrabarty","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Sanjeev","family":"Khanna","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","reference":[{"key":"7_CR1","doi-asserted-by":"crossref","unstructured":"Archer, A.: Two O(log* k)-approximation algorithms for the asymmetric k-center problem. In: Proceedings, MPS Conference on Integer Programming and Combinatorial Optimization (IPCO), pp. 1\u201314 (2010)","DOI":"10.1007\/3-540-45535-3_1"},{"key":"7_CR2","doi-asserted-by":"crossref","unstructured":"Bartal, Y.: On approximating arbitrary metrices by tree metrics. In: ACM Symp. on Theory of Computing (STOC), pp. 161\u2013168 (1998)","DOI":"10.1145\/276698.276725"},{"key":"7_CR3","unstructured":"Bhalgat, A., Chakrabarty, D., Khanna, S.: Optimal lower bounds for universal and differentially private steiner trees and tsps. Technical report, http:\/\/arxiv.org\/abs\/1011.3770"},{"key":"7_CR4","doi-asserted-by":"crossref","unstructured":"Dwork, C.: Differential privacy. In: Proceedings, International Colloquium on Automata, Languages and Processing, pp. 1\u201312 (2006)","DOI":"10.1007\/11787006_1"},{"key":"7_CR5","doi-asserted-by":"crossref","unstructured":"Fakcharoenphol, J., Rao, S., Talwar, K.: A tight bound on approximating arbitrary metrics by tree metrics. In: ACM Symp. on Theory of Computing (STOC), pp. 448\u2013455 (2003)","DOI":"10.1145\/780542.780608"},{"key":"7_CR6","doi-asserted-by":"crossref","unstructured":"Gorodezky, I., Kleinberg, R.D., Shmoys, D.B., Spencer, G.: Improved lower bounds for the universal and a priori tsp. In: Proceedings, International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, pp. 178\u2013191 (2010)","DOI":"10.1007\/978-3-642-15369-3_14"},{"key":"7_CR7","doi-asserted-by":"crossref","unstructured":"Gupta, A., Hajiaghayi, M., R\u00e4cke, H.: Oblivious network design. In: Proceedings, ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 970\u2013979 (2006)","DOI":"10.1145\/1109557.1109665"},{"key":"7_CR8","doi-asserted-by":"crossref","unstructured":"Gupta, A., Ligett, K., McSherry, F., Roth, A., Talwar, K.: Differentially private approximation algorithms. In: Proceedings, ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 1106\u20131125 (2010)","DOI":"10.1137\/1.9781611973075.90"},{"key":"7_CR9","doi-asserted-by":"crossref","unstructured":"Hajiaghayi, M., Kleinberg, R., Leighton, F.T.: Improved lower and upper bounds for universal tsp in planar metrics. In: Proceedings, ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 649\u2013658 (2006)","DOI":"10.1145\/1109557.1109628"},{"issue":"4","key":"7_CR10","doi-asserted-by":"publisher","first-page":"439","DOI":"10.1090\/S0273-0979-06-01126-8","volume":"43","author":"S. Hoory","year":"2006","unstructured":"Hoory, S., Linial, N., Wigderson, A.: Expander graphs and their applications. Bull. of the Amer. Soc.\u00a043(4), 439\u2013561 (2006)","journal-title":"Bull. of the Amer. Soc."},{"issue":"3","key":"7_CR11","doi-asserted-by":"publisher","first-page":"369","DOI":"10.1137\/0404033","volume":"4","author":"M. Imase","year":"1991","unstructured":"Imase, M., Waxman, B.M.: Dynamic steiner tree problem. SIAM J. Discrete Math.\u00a04(3), 369\u2013384 (1991)","journal-title":"SIAM J. Discrete Math."},{"key":"7_CR12","doi-asserted-by":"crossref","unstructured":"Jia, L., Lin, G., Noubir, G., Rajaraman, R., Sundaram, R.: Universal approximations for tsp, steiner tree, and set cover. In: ACM Symp. on Theory of Computing (STOC), pp. 386\u2013395 (2005)","DOI":"10.1145\/1060590.1060649"},{"key":"7_CR13","doi-asserted-by":"crossref","unstructured":"Leighton, F.T., Rao, S.: An approximate max-flow min-cut theorem for uniform multicommodity flow problems with application to approximation algorithms. In: Proceedings, IEEE Symposium on Foundations of Computer Science (FOCS), pp. 422\u2013431 (1988)","DOI":"10.1109\/SFCS.1988.21958"},{"issue":"2","key":"7_CR14","doi-asserted-by":"publisher","first-page":"215","DOI":"10.1007\/BF01200757","volume":"15","author":"N. Linial","year":"1995","unstructured":"Linial, N., London, E., Rabinovich, Y.: The geometry of graphs and some of its algorithmic applications. Combinatorica\u00a015(2), 215\u2013246 (1995)","journal-title":"Combinatorica"},{"key":"7_CR15","doi-asserted-by":"publisher","first-page":"261","DOI":"10.1007\/BF02126799","volume":"4","author":"A. Lubotzky","year":"1988","unstructured":"Lubotzky, A., Phillips, R., Sarnak, P.: Ramanujan graphs. Combinatorica\u00a04, 261\u2013277 (1988)","journal-title":"Combinatorica"},{"key":"7_CR16","doi-asserted-by":"crossref","unstructured":"Moitra, A.: Approximation algorithms for multicommodity-type problems with guarantees independent of the graph size. In: Proceedings, IEEE Symposium on Foundations of Computer Science (FOCS), pp. 3\u201312 (2009)","DOI":"10.1109\/FOCS.2009.28"},{"key":"7_CR17","doi-asserted-by":"crossref","unstructured":"Moitra, A., Leighton, F.T.: Extensions and limits to vertex sparsification. In: ACM Symp. on Theory of Computing (STOC), pp. 47\u201356 (2010)","DOI":"10.1145\/1806689.1806698"},{"issue":"2","key":"7_CR18","doi-asserted-by":"publisher","first-page":"259","DOI":"10.1006\/jagm.1997.0921","volume":"27","author":"R. Panigrahy","year":"1998","unstructured":"Panigrahy, R., Vishwanathan, S.: An O(log* n) approximation algorithm for the asymmetric p-center problem. J. Algorithms\u00a027(2), 259\u2013268 (1998)","journal-title":"J. Algorithms"},{"key":"7_CR19","unstructured":"Talwar, K.: Problem 1. In: Open Problem in Bellairs Workshop on Approximation Algorithms, Barbados (2010), http:\/\/www.math.mcgill.ca\/~vetta\/Workshop\/openproblems2.pdf"},{"key":"7_CR20","doi-asserted-by":"crossref","unstructured":"Yao, A.C.-C.: Probabilistic computations: Towards a unified measure of complexity. In: Proceedings, IEEE Symposium on Foundations of Computer Science (FOCS), pp. 222\u2013227 (1977)","DOI":"10.1109\/SFCS.1977.24"}],"container-title":["Lecture Notes in Computer Science","Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-22935-0_7","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,6,13]],"date-time":"2019-06-13T21:03:21Z","timestamp":1560459801000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-22935-0_7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011]]},"ISBN":["9783642229343","9783642229350"],"references-count":20,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-22935-0_7","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2011]]}}}