On the Approximability of Geometric and Geographic Generalization and the Min-Max Bin Covering Problem

Details On the Approximability of Geometric and Geographic Generalization and the Min-Max Bin Covering Problem On the Approximability of Geometric and Geographic Generalization and the Min-Max Bin Covering Problem

2009-04-23

arxiv.org/abs/0904.3756v3

Computer Science

Data Structures and Algorithms

18 pages. Expanded version of paper appearing in 2009 Algorithms and Data Structures Symposium (formerly WADS)

Scientific paper

We study the problem of abstracting a table of data about individuals so that no selection query can identify fewer than k individuals. We show that it is impossible to achieve arbitrarily good polynomial-time approximations for a number of natural variations of the generalization technique, unless P = NP, even when the table has only a single quasi-identifying attribute that represents a geographic or unordered attribute: Zip-codes: nodes of a planar graph generalized into connected subgraphs GPS coordinates: points in R2 generalized into non-overlapping rectangles Unordered data: text labels that can be grouped arbitrarily. In addition to impossibility results, we provide approximation algorithms for these difficult single-attribute generalization problems, which, of course, apply to multiple-attribute instances with one that is quasi-identifying. We show theoretically and experimentally that our approximation algorithms can come reasonably close to optimal solutions. Incidentally, the generalization problem for unordered data can be viewed as a novel type of bin packing problem--min-max bin covering--which may be of independent interest.

Affiliated with

Also associated with

No associations

Rating

On the Approximability of Geometric and Geographic Generalization and the Min-Max Bin Covering Problem does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with On the Approximability of Geometric and Geographic Generalization and the Min-Max Bin Covering Problem, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On the Approximability of Geometric and Geographic Generalization and the Min-Max Bin Covering Problem will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-608469