David Eppstein - Publications

Papers 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)

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

Semi-automatically filtered from a common source file.