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

Simple item page
dc.creatorDu, Wenliang
dc.creatorEppstein, David
dc.creatorGoodrich, Michael T.
dc.creatorLueker, George S.
dc.date2009-04-23
dc.date2009-05-12
dc.date.accessioned2026-07-07T13:13:27Z
dc.date.available2026-07-07T13:13:27Z
dc.descriptionWe 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.
dc.description18 pages. Expanded version of paper appearing in 2009 Algorithms and Data Structures Symposium (formerly WADS)
dc.identifierhttps://arxiv.org/abs/0904.3756
dc.identifierhttp://arxiv.org/abs/0904.3756
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/229892
dc.subjectData Structures and Algorithms
dc.titleOn the Approximability of Geometric and Geographic Generalization and the Min-Max Bin Covering Problem
dc.typetext

Files

Collections

arXiv