On the Complexity of the $k$-Anonymization Problem

Venkatesan T. Chakaravarthy, Vinayaka Pandit, Yogish Sabharwal

We study the problem of anonymizing tables containing personal information before releasing them for public use. One of the formulations considered in this context is the $k$-anony…