David Eppstein - Publications

Publications with Wenliang (Kevin) Du

• On the approximability of geometric and geographic generalization and the min-max bin covering problem.
  W. Du, D. Eppstein, M. T. Goodrich, G. Lueker.
  arXiv:0904.3756.
  Algorithms and Data Structures Symposium (WADS), Banff, Canada.
  Springer, Lecture Notes in Comp. Sci. 5664, 2009, pp. 242–253.

  We investigate several simplified models for k-anonymization in databases, show them to be hard to solve exactly, and provide approximation algorithms for them.

  The min-max bin covering problem is closely related to one of our models. An input to this problem consists of a collection of items with sizes and a threshold size. The items must be grouped into bins such that the total size within each bin is at least the threshold, while keeping the maximum bin size as small as possible.

  (Slides)