David Eppstein - Publications

Publications with Dan Hirschberg

• Choosing subsets with maximum weighted average.
  D. Eppstein and D. S. Hirschberg.
  Tech. Rep. 95-12, ICS, UCI, 1995.
  5th MSI Worksh. on Computational Geometry, 1995, pp. 7–8.
  J. Algorithms 24: 177–193, 1997.

  Uses geometric optimization techniques to find, among n weighted values, the k to drop so as to maximize the weighted average of the remaining values. The feasibility test for the corresponding decision problem involves k-sets in a dual line arrangement.

  (Full paper)

• Geometric thickness of complete graphs.
  M. Dillencourt, D. Eppstein, and D. S. Hirschberg.
  6th Int. Symp. Graph Drawing, Montreal, August 1998.
  Springer, Lecture Notes in Comp. Sci. 1547, 1998, pp. 102–110.
  arXiv:math.CO/9910185.
  J. Graph Algorithms and Applications 4 (3): 5–17, 2000 (special issue for GD98).

  We define a notion of geometric thickness, intermediate between the previously studied concepts of graph thickness and book thickness: a graph has geometric thickness T if its vertices can be embedded in the plane, and its edges partitioned into T subsets, so that each subset forms a planar straight line graph. We then give upper and lower bounds on the geometric thickness of complete graphs.

• Improved combinatorial group testing for real-world problem sizes.
  D. Eppstein, M. T. Goodrich, and D. S. Hirschberg.
  9th Worksh. Algorithms and Data Structures, Waterloo, 2005.
  Springer, Lecture Notes in Comp. Sci. 3608, 2005, pp. 86–98.
  arXiv:cs.DS/0505048.
  SIAM J. Computing 36 (5): 1360–1375, 2007.

  We study practically efficient methods for finding few flawed items among large sets of items, by testing whether there exist flaws in each of a small number of batches of items.

  (Mike's WADS talk slides)

• Combinatorial pair testing: distinguishing workers from slackers.
  D. Eppstein, M. T. Goodrich, and D. S. Hirschberg.
  arXiv:1305.0110.
  13th Int. Symp. Algorithms and Data Structures (WADS 2013), London, Ontario.
  Springer, Lecture Notes in Comp. Sci. 8037, 2013, pp. 316–327.
  

  We study the problem of distinguishing workers (people who complete their assigned tasks) from slackers (people who do not contribute towards the completion of their tasks) by grouping people in pairs and assigning a task to each group.

• From discrepancy to majority.
  D. Eppstein and D. S. Hirschberg.
  arXiv:1512.06488.
  Proc. 12th Latin American Theoretical Informatics Symposium (LATIN 2016), Ensenada, Mexico.
  Springer, Lecture Notes in Comp. Sci. 9644 (2016), pp. 390–402.
  Algorithmica 80 (4): 1278–1297, 2018.

  We provide upper and lower bounds on the query complexity of a problem in which the input is a collection of two-colored items, and the problem is to either find an item of the majority color or to determine that there is no majority, by performing queries that determine the discrepancy of fixed-size subsets of the items.

  (Slides)