| Anonymizing Binary Tables is APX-hard (2007) | |||||||||
Abstract | |||||||||
| The problem of publishing personal data without giving up privacy is increasingly important. An interesting formalization is the $k$-anonymization, where all rows in a table are clustered in sets of at least $k$ records, and all the entries for which records in the same cluster have different values are suppressed. The problem has been shown to be NP-hard when the records values are over a ternary alphabet and $k=3$. In this paper we show that the problem is not only NP-hard, but also APX-hard, when the records values are over a binary alphabet and $k=3$. | |||||||||
Publication details | |||||||||
| |||||||||