{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,1]],"date-time":"2026-04-01T18:21:56Z","timestamp":1775067716152,"version":"3.50.1"},"publisher-location":"Berlin, Heidelberg","reference-count":33,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783642374869","type":"print"},{"value":"9783642374876","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2013]]},"DOI":"10.1007\/978-3-642-37487-6_26","type":"book-chapter","created":{"date-parts":[[2013,4,17]],"date-time":"2013-04-17T03:55:02Z","timestamp":1366170902000},"page":"331-345","source":"Crossref","is-referenced-by-count":20,"title":["On the Complexity of t-Closeness Anonymization and Related Problems"],"prefix":"10.1007","author":[{"given":"Hongyu","family":"Liang","sequence":"first","affiliation":[]},{"given":"Hao","family":"Yuan","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"26_CR1","doi-asserted-by":"crossref","unstructured":"Aggarwal, G., Feder, T., Motwani, K.K.R., Panigrahy, R., Thomas, D., Zhu, A.: Anonymizing tables. In: ICDT, pp. 246\u2013258 (2005)","DOI":"10.1007\/978-3-540-30570-5_17"},{"issue":"3","key":"26_CR2","doi-asserted-by":"publisher","first-page":"678","DOI":"10.1137\/090752699","volume":"40","author":"E. Anshelevich","year":"2011","unstructured":"Anshelevich, E., Karagiozova, A.: Terminal backup, 3D matching, and covering cubic graphs. SIAM Journal on Computing\u00a040(3), 678\u2013708 (2011)","journal-title":"SIAM Journal on Computing"},{"key":"26_CR3","doi-asserted-by":"crossref","unstructured":"Baig, M.M., Li, J., Liu, J., Wang, H.: Cloning for privacy protection in multiple independent data publications. In: CIKM, pp. 885\u2013894 (2011)","DOI":"10.1145\/2063576.2063705"},{"key":"26_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"393","DOI":"10.1007\/978-3-642-14162-1_33","volume-title":"Automata, Languages and Programming","author":"J. Blocki","year":"2010","unstructured":"Blocki, J., Williams, R.: Resolving the complexity of some data privacy problems. In: Abramsky, S., Gavoille, C., Kirchner, C., Meyer auf der Heide, F., Spirakis, P.G. (eds.) ICALP 2010, Part II. LNCS, vol.\u00a06199, pp. 393\u2013404. Springer, Heidelberg (2010)"},{"issue":"1","key":"26_CR5","doi-asserted-by":"publisher","first-page":"97","DOI":"10.1007\/s10878-009-9277-y","volume":"22","author":"P. Bonizzoni","year":"2011","unstructured":"Bonizzoni, P., Vedova, G.D., Dondi, R.: Anonymizing binary and small tables is hard to approximate. Journal of Combinatorial Optimization\u00a022(1), 97\u2013119 (2011)","journal-title":"Journal of Combinatorial Optimization"},{"key":"26_CR6","unstructured":"Bonizzoni, P., Vedova, G.D., Dondi, R., Pirola, Y.: Parameterized complexity of k-anonymity: hardness and tractability. Journal of Combinatorial Optimization (in press)"},{"key":"26_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"53","DOI":"10.1007\/978-3-642-22953-4_5","volume-title":"Fundamentals of Computation Theory","author":"R. Bredereck","year":"2011","unstructured":"Bredereck, R., Nichterlein, A., Niedermeier, R., Philip, G.: The effect of homogeneity on the complexity of k-anonymity. In: Owe, O., Steffen, M., Telle, J.A. (eds.) FCT 2011. LNCS, vol.\u00a06914, pp. 53\u201364. Springer, Heidelberg (2011)"},{"issue":"1","key":"26_CR8","doi-asserted-by":"publisher","first-page":"59","DOI":"10.1007\/s00778-010-0191-9","volume":"20","author":"J. Cao","year":"2011","unstructured":"Cao, J., Karras, P., Kalnis, P., Tan, K.-L.: SABRE: a sensitive attribute bucketization and redistribution framework for t-closeness. The VLDB Journal\u00a020(1), 59\u201381 (2011)","journal-title":"The VLDB Journal"},{"key":"26_CR9","doi-asserted-by":"crossref","unstructured":"Dondi, R., Mauri, G., Zoppis, I.: The l-diversity problem: Tractability and approximability. Theoretical Computer Science (2012) (in press), doi:10.1016\/j.tcs.2012.05.024","DOI":"10.1016\/j.tcs.2012.05.024"},{"key":"26_CR10","doi-asserted-by":"crossref","unstructured":"Downey, R.G., Fellows, M.R.: Parameterized Complexity. Springer (1999)","DOI":"10.1007\/978-1-4612-0515-9"},{"issue":"4","key":"26_CR11","doi-asserted-by":"publisher","first-page":"362","DOI":"10.1007\/s10878-009-9253-6","volume":"18","author":"P.A. Evans","year":"2009","unstructured":"Evans, P.A., Wareham, T., Chaytor, R.: Fixed-parameter tractability of anonymizing data by suppressing entries. Journal of Combinatorial Optimization\u00a018(4), 362\u2013375 (2009)","journal-title":"Journal of Combinatorial Optimization"},{"key":"26_CR12","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman (1979)"},{"key":"26_CR13","doi-asserted-by":"crossref","unstructured":"Garey, M.R., Johnson, D.S., Stockmeyer, L.: Some simplified NP-complete problems. In: STOC, pp. 47\u201363 (1974)","DOI":"10.1145\/800119.803884"},{"key":"26_CR14","doi-asserted-by":"crossref","unstructured":"LeFevre, K., DeWitt, D.J., Ramakrishnan, R.: Incognito: Efficient full-domain k-anonymity. In: SIGMOD, pp. 49\u201360 (2005)","DOI":"10.1145\/1066157.1066164"},{"key":"26_CR15","doi-asserted-by":"crossref","unstructured":"LeFevre, K., DeWitt, D.J., Ramakrishnan, R.: Mondrian multidimensional k-anonymity. In: ICDE (2006)","DOI":"10.1109\/ICDE.2006.101"},{"key":"26_CR16","doi-asserted-by":"crossref","unstructured":"Li, N., Li, T., Venkatasubramanian, S.: t-Closeness: Privacy beyond k-Anonymity and l-Diversity. In: ICDE, pp. 106\u2013115 (2007)","DOI":"10.1109\/ICDE.2007.367856"},{"issue":"7","key":"26_CR17","doi-asserted-by":"publisher","first-page":"943","DOI":"10.1109\/TKDE.2009.139","volume":"22","author":"N. Li","year":"2010","unstructured":"Li, N., Li, T., Venkatasubramanian, S.: Closeness: A new privacy measure for data publishing. IEEE Transactions on Knowledge and Data Engineering\u00a022(7), 943\u2013956 (2010)","journal-title":"IEEE Transactions on Knowledge and Data Engineering"},{"key":"26_CR18","unstructured":"Liang, H., Yuan, H.: On the complexity of t-closeness anonymization and related problems. Technical report (2012), \n                    \n                      http:\/\/arxiv.org\/abs\/1301.1751"},{"key":"26_CR19","doi-asserted-by":"crossref","unstructured":"Machanavajjhala, A., Kifer, D., Gehrke, J., Venkitasubramaniam, M.: l-diversity: Privacy beyond k-anonymity. ACM Trans. Knowl. Discov. Data (TKDD)\u00a01(1) (2007)","DOI":"10.1145\/1217299.1217302"},{"key":"26_CR20","doi-asserted-by":"crossref","unstructured":"Martin, D.J., Kifer, D., Machanavajjhala, A., Gehrke, J., Halpern, J.Y.: Worst-case background knowledge for privacy preserving data publishing. In: ICDE, pp. 126\u2013135 (2007)","DOI":"10.1109\/ICDE.2007.367858"},{"key":"26_CR21","doi-asserted-by":"crossref","unstructured":"Meyerson, A., Williams, R.: On the complexity of optimal k-anonymity. In: PODS (2004)","DOI":"10.1145\/1055558.1055591"},{"key":"26_CR22","doi-asserted-by":"crossref","unstructured":"Mohammed, N., Chen, R., Fung, B.C.M., Yu, P.S.: Differentially private data release for data mining. In: KDD (2011)","DOI":"10.1145\/2020408.2020487"},{"key":"26_CR23","doi-asserted-by":"crossref","unstructured":"Nergiz, M.E., Atzori, M., Clifton, C.: Hiding the presence of individuals from shared databases. In: SIGMOD, pp. 665\u2013676 (2007)","DOI":"10.1145\/1247480.1247554"},{"key":"26_CR24","doi-asserted-by":"crossref","unstructured":"Park, H., Shim, K.: Approximate algorithms for k-anonymity. In: SIGMOD (2007)","DOI":"10.1145\/1247480.1247490"},{"issue":"11","key":"26_CR25","doi-asserted-by":"publisher","first-page":"1623","DOI":"10.1109\/TKDE.2009.190","volume":"22","author":"D. Rebollo-Monedero","year":"2010","unstructured":"Rebollo-Monedero, D., Forn\u00e9, J., Domingo-Ferrer, J.: From t-closeness-like privacy to postrandomization via information theory. IEEE Transactions on Knowledge and Data Engineering\u00a022(11), 1623\u20131636 (2010)","journal-title":"IEEE Transactions on Knowledge and Data Engineering"},{"issue":"2","key":"26_CR26","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1023\/A:1026543900054","volume":"40","author":"Y. Rubner","year":"2000","unstructured":"Rubner, Y., Tomasi, C., Guibas, L.J.: The earth mover\u2019s distance as a metric for image retrieval. International Journal of Computer Vision\u00a040(2), 99\u2013121 (2000)","journal-title":"International Journal of Computer Vision"},{"issue":"6","key":"26_CR27","doi-asserted-by":"publisher","first-page":"1010","DOI":"10.1109\/69.971193","volume":"13","author":"P. Samarati","year":"2001","unstructured":"Samarati, P.: Protecting respondents\u2019 identities in microdata release. IEEE Transactions on Knowledge and Data Engineering\u00a013(6), 1010\u20131027 (2001)","journal-title":"IEEE Transactions on Knowledge and Data Engineering"},{"issue":"5","key":"26_CR28","doi-asserted-by":"publisher","first-page":"557","DOI":"10.1142\/S0218488502001648","volume":"10","author":"L. Sweeney","year":"2002","unstructured":"Sweeney, L.: k-anonymity: a model for protecting privacy. International Journal of Uncertainty, Fuzziness and Knowledge-Based Systems\u00a010(5), 557\u2013570 (2002)","journal-title":"International Journal of Uncertainty, Fuzziness and Knowledge-Based Systems"},{"key":"26_CR29","doi-asserted-by":"crossref","unstructured":"Xiao, X., Tao, Y.: Personalized privacy preservation. In: SIGMOD, pp. 229\u2013240 (2006)","DOI":"10.1145\/1142473.1142500"},{"key":"26_CR30","doi-asserted-by":"crossref","unstructured":"Xiao, X., Tao, Y.: m-invariance: Towards privacy preserving re-publication of dynamic datasets. In: SIGMOD, pp. 689\u2013700 (2007)","DOI":"10.1145\/1247480.1247556"},{"key":"26_CR31","doi-asserted-by":"crossref","unstructured":"Xiao, X., Yi, K., Tao, Y.: The hardness and approximation algorithms for l-diversity. In: EDBT, pp. 135\u2013146 (2010)","DOI":"10.1145\/1739041.1739060"},{"key":"26_CR32","doi-asserted-by":"crossref","unstructured":"Xue, M., Karras, P., Raissi, C., Pung, H.K.: Utility-driven anonymization in data publishing. In: CIKM, pp. 2277\u20132280 (2011)","DOI":"10.1145\/2063576.2063945"},{"key":"26_CR33","doi-asserted-by":"crossref","unstructured":"Zhang, Q., Koudas, N., Srivastava, D., Yu, T.: Aggregate query answering on anonymized tables. In: ICDE, pp. 116\u2013125 (2007)","DOI":"10.1109\/ICDE.2007.367857"}],"container-title":["Lecture Notes in Computer Science","Database Systems for Advanced Applications"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-37487-6_26","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,12]],"date-time":"2019-05-12T07:34:51Z","timestamp":1557646491000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-37487-6_26"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013]]},"ISBN":["9783642374869","9783642374876"],"references-count":33,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-37487-6_26","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013]]}}}