Optimization-Based k-Anonymity Algorithms

In this paper we present a formulation of k-anonymity as a mathematical optimization problem. In solving this formulated problem, k-anonymity is achieved while maximizing the utility of the resulting dataset. Our formulation has the advantage of incorporating different weights for attributes in order to achieve customized utility to suit different research purposes. The resulting formulation is a Mixed Integer Linear Program (MILP), which is NP-complete in general. Recognizing the complexity of the problem, we propose two practical algorithms which can provide near-optimal utility. Our experimental evaluation confirms that our algorithms are scalable when used for datasets containing large numbers of records.