{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T04:51:53Z","timestamp":1725511913057},"publisher-location":"Berlin, Heidelberg","reference-count":22,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540709350"},{"type":"electronic","value":"9783540709367"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/978-3-540-70936-7_21","type":"book-chapter","created":{"date-parts":[[2007,5,16]],"date-time":"2007-05-16T07:43:44Z","timestamp":1179301424000},"page":"383-403","source":"Crossref","is-referenced-by-count":2,"title":["Private Approximation of Clustering and Vertex Cover"],"prefix":"10.1007","author":[{"given":"Amos","family":"Beimel","sequence":"first","affiliation":[]},{"given":"Renen","family":"Hallak","sequence":"additional","affiliation":[]},{"given":"Kobbi","family":"Nissim","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"21_CR1","doi-asserted-by":"crossref","unstructured":"Beimel, A., Carmi, P., Nissim, K., Weinreb, E.: Private approximation of search problems. In: Proc. of the 38th STOC, pp. 119\u2013128 (2006)","DOI":"10.1145\/1132516.1132533"},{"key":"21_CR2","doi-asserted-by":"crossref","unstructured":"Ben-Or, M., Goldwasser, S., Wigderson, A.: Completeness theorems for noncryptographic fault-tolerant distributed computations. In: Proc. of the 20th STOC, pp. 1\u201310 (1988)","DOI":"10.1145\/62212.62213"},{"key":"21_CR3","doi-asserted-by":"crossref","first-page":"305","DOI":"10.1137\/0206023","volume":"6","author":"L. Berman","year":"1977","unstructured":"Berman, L., Hartmanis, J.: On isomorphisms and density of NP and other complete sets. SICOMP\u00a06, 305\u2013322 (1977)","journal-title":"SICOMP"},{"key":"21_CR4","doi-asserted-by":"crossref","unstructured":"Blum, A., Dwork, C., McSherry, F., Nissim, K.: Practical privacy: the SuLQ framework. In: Proc. of the 24th PODS, pp. 128\u2013138 (2005)","DOI":"10.1145\/1065167.1065184"},{"key":"21_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"120","DOI":"10.1007\/3-540-44436-X_13","volume-title":"Approximation Algorithms for Combinatorial Optimization","author":"U. Feige","year":"2000","unstructured":"Feige, U., Langberg, M., Nissim, K.: On the hardness of approximating NP witnesses. In: Jansen, K., Khuller, S. (eds.) APPROX 2000. LNCS, vol.\u00a01913, pp. 120\u2013131. Springer, Heidelberg (2000)"},{"issue":"3","key":"21_CR6","doi-asserted-by":"publisher","first-page":"435","DOI":"10.1145\/1159892.1159900","volume":"2","author":"J. Feigenbaum","year":"2006","unstructured":"Feigenbaum, J., Ishai, Y., Malkin, T., Nissim, K., Strauss, M.J., Wright, R.N.: Secure multiparty computation of approximations. TALG\u00a02(3), 435\u2013472 (2006)","journal-title":"TALG"},{"key":"21_CR7","series-title":"Lecture Notes in Computer Science","first-page":"1","volume-title":"Advances in Cryptology - EUROCRYPT 2004","author":"M.J. Freedman","year":"2004","unstructured":"Freedman, M.J., Nissim, K., Pinkas, B.: Efficient private matching and set intersection. In: Cachin, C., Camenisch, J.L. (eds.) EUROCRYPT 2004. LNCS, vol.\u00a03027, pp. 1\u201319. Springer, Heidelberg (2004)"},{"key":"21_CR8","doi-asserted-by":"crossref","unstructured":"Goldreich, O., Micali, S., Wigderson, A.: How to play any mental game. In: Proc. of the 19th STOC, pp. 218\u2013229 (1987)","DOI":"10.1145\/28395.28420"},{"key":"21_CR9","doi-asserted-by":"publisher","first-page":"293","DOI":"10.1016\/0304-3975(85)90224-5","volume":"38","author":"T.F. Gonzalez","year":"1985","unstructured":"Gonzalez, T.F.: Clustering to minimize the maximum inter-cluster distance. TCS\u00a038, 293\u2013306 (1985)","journal-title":"TCS"},{"key":"21_CR10","doi-asserted-by":"crossref","unstructured":"Halevi, S., Krauthgamer, R., Kushilevitz, E., Nissim, K.: Private approximation of NP-hard functions. In: Proc. of the 33th STOC, pp. 550\u2013559 (2001)","DOI":"10.1145\/380752.380850"},{"key":"21_CR11","doi-asserted-by":"publisher","first-page":"533","DOI":"10.1145\/5925.5933","volume":"33","author":"D.S. Hochbaum","year":"1986","unstructured":"Hochbaum, D.S., Shmoys, D.B.: A unified approach to approximation algorithms for bottleneck problems. JACM\u00a033, 533\u2013550 (1986)","journal-title":"JACM"},{"key":"21_CR12","first-page":"209","volume":"1","author":"W.L. Hsu","year":"1979","unstructured":"Hsu, W.L., Nemhauser, G.L.: Easy and hard bottleneck location problems. DAM\u00a01, 209\u2013216 (1979)","journal-title":"DAM"},{"key":"21_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"245","DOI":"10.1007\/11681878_13","volume-title":"Theory of Cryptography","author":"P. Indyk","year":"2006","unstructured":"Indyk, P., Woodruff, D.: Polylogarithmic private approximations and efficient matching. In: Halevi, S., Rabin, T. (eds.) TCC 2006. LNCS, vol.\u00a03876, pp. 245\u2013264. Springer, Heidelberg (2006)"},{"key":"21_CR14","doi-asserted-by":"publisher","first-page":"513","DOI":"10.1137\/0137040","volume":"37","author":"O. Kariv","year":"1979","unstructured":"Kariv, O., Hakimi, S.L.: An algorithmic approach to network location problems, part I: the p-centers. SIAM J. Appl. Math.\u00a037, 513\u2013538 (1979)","journal-title":"SIAM J. Appl. Math."},{"key":"21_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"283","DOI":"10.1007\/978-3-540-30576-7_16","volume-title":"Theory of Cryptography","author":"E. Kiltz","year":"2005","unstructured":"Kiltz, E., Leander, G., Malone-Lee, J.: Secure computation of the mean and related statistics. In: Kilian, J. (ed.) TCC 2005. LNCS, vol.\u00a03378, pp. 283\u2013302. Springer, Heidelberg (2005)"},{"key":"21_CR16","doi-asserted-by":"crossref","unstructured":"Kumar, R., Sivakumar, D.: Proofs, codes, and polynomial-time reducibilities. In: Proc. of the 14th CCC, pp. 46\u201353 (1999)","DOI":"10.1109\/CCC.1999.766261"},{"key":"21_CR17","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511813603","volume-title":"Probability and Computing","author":"M. Mitzenmacher","year":"2005","unstructured":"Mitzenmacher, M., Upfal, E.: Probability and Computing. Cambridge University Press, Cambridge (2005)"},{"key":"21_CR18","first-page":"445","volume":"25","author":"J. Plesnik","year":"1980","unstructured":"Plesnik, J.: On the computational complexity of centers locating in a graph. Aplikace Matematiky\u00a025, 445\u2013452 (1980)","journal-title":"Aplikace Matematiky"},{"key":"21_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"480","DOI":"10.1007\/3-540-08342-1_37","volume-title":"Automata, Languages and Programming","author":"J. Simon","year":"1977","unstructured":"Simon, J.: On the difference between one and many. In: Salomaa, A., Steinby, M. (eds.) Automata, Languages and Programming. LNCS, vol.\u00a052, pp. 480\u2013491. Springer, Heidelberg (1977)"},{"key":"21_CR20","volume-title":"A reduction from satisfiability to Hamiltonian circuits that preserves the number of solutions","author":"L.G. Valiant","year":"1974","unstructured":"Valiant, L.G.: A reduction from satisfiability to Hamiltonian circuits that preserves the number of solutions (Manuscript). Leeds Press, Leeds (1974)"},{"key":"21_CR21","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1016\/0304-3975(86)90135-0","volume":"47","author":"L.G. Valiant","year":"1986","unstructured":"Valiant, L.G., Vazirani, V.V.: NP is as easy as detecting unique solutions. TCS\u00a047, 85\u201393 (1986)","journal-title":"TCS"},{"key":"21_CR22","doi-asserted-by":"crossref","unstructured":"Yao, A.C.: Protocols for secure computations. In: Proc. of the 23th FOCS, pp. 160\u2013164 (1982)","DOI":"10.1109\/SFCS.1982.38"}],"container-title":["Lecture Notes in Computer Science","Theory of Cryptography"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-70936-7_21.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,19]],"date-time":"2020-11-19T00:12:54Z","timestamp":1605744774000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-70936-7_21"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["9783540709350","9783540709367"],"references-count":22,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-70936-7_21","relation":{},"subject":[]}}