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.

  (BibTeX -- Full paper -- CiteSeer -- ACM DL)

• Geometric thickness of complete graphs.
  M. Dillencourt, D. Eppstein, and D. S. Hirschberg.
  6th Int. Symp. Graph Drawing, Montreal, August 1998.
  Lecture Notes in Comp. Sci. 1547, 1998, pp. 102-110, © Springer-Verlag.
  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.

  (Springer abstract -- BibTeX -- CiteSeer -- Citations -- ACM DL -- GDEA)

• 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.
  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.

  (BibTeX -- 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, to appear.

  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.

Co-authors -- Publications -- David Eppstein -- Theory Group -- Inf. & Comp. Sci. -- UC Irvine

Semi-automatically filtered from a common source file.