David Eppstein - Publications

Surveys

• Parallel algorithmic techniques for combinatorial computation.
  D. Eppstein and Z. Galil.
  Ann. Rev. Comput. Sci. 3:233-283, 1988.
  Invited talk by Z. Galil, 16th Int. Coll. Automata, Languages and Programming, Stresa, Italy, 1989.
  Lecture Notes in Comp. Sci. 372, 1989, pp. 304-318, © Springer-Verlag.

  This survey on parallel algorithms emphasized the use of basic subroutines such as prefix sums, Euler tours, ear decomposition, and matrix multiplication for solving more complicated graph problems.

  (BibTeX -- Citations -- CiteSeer -- ACM DL (ARCS) -- ACM DL (ICALP))

• Efficient algorithms for sequence analysis.
  D. Eppstein, Z. Galil, R. Giancarlo, and G.F. Italiano.
  International Advanced Workshop on Sequences, Positano, Italy, 1991.
  Sequences II: Methods in Communication, Security, and Computer Science, R.M. Capocelli, A. De Santis, and U. Vaccaro, eds., Springer-Verlag, 1993, pp. 225-244.
  

  Surveys results on speeding up certain dynamic programs used for sequence comparison and RNA structure prediction.

  (BibTeX -- Citations -- CiteSeer)

• Ten algorithms for Egyptian fractions.
  D. Eppstein.
  Mathematica in Education and Research 4(2):5-15, 1995.

  Number theory. I survey and implement in Mathematica several methods for representing rational numbers as sums of distinct unit fractions. One of the methods involves searching for paths in a certain graph using a k shortest paths heuristic.

  (BibTeX -- Citations -- Also available in HTML and Mathematica notebook formats)

• Mesh generation and optimal triangulation.
  M. Bern and D. Eppstein.
  Tech. Rep. CSL-92-1, Xerox PARC, 1992.
  Computing in Euclidean Geometry, D.-Z. Du and F.K. Hwang, eds., World Scientific, 1992, pp. 23-90.
  Revised version in Computing in Euclidean Geometry, 2nd ed., D.-Z. Du and F.K. Hwang, eds., World Scientific, 1995, pp. 47-123.

  Considers both heuristics and theoretical algorithms for finding good triangulations and tetrahedralizations for surface interpolation and unstructured finite element meshes. Note that the online copy here omits the figures; also online is this paper's bibliography.

  (BibTeX -- Citations -- CiteSeer)

• Approximation algorithms for geometric problems.
  M. Bern and D. Eppstein.
  Approximation Algorithms for NP-hard Problems, D. Hochbaum, ed., PWS Publishing, 1996, pp. 296-345.

  Considers problems for which no polynomial-time exact algorithms are known, and concentrates on bounds for worst-case approximation ratios, especially those depending intrinsically on geometry rather than on more general graph theoretic or metric space formulations. Includes sections on the traveling salesman problem, Steiner trees, minimum weight triangulation, clustering, and separation problems.

  (BibTeX -- Citations -- ACM DL)

• Spanning trees and spanners.
  D. Eppstein.
  Tech. Rep. 96-16, ICS, UCI, 1996.
  Handbook of Computational Geometry, J.-R. Sack and J. Urrutia, eds., Elsevier, 1999, pp. 425-461.

  Surveys results in geometric network design theory, including algorithms for constructing minimum spanning trees and low-dilation graphs.

  (BibTeX -- Citations -- CiteSeer)

• Quasiconvex programming.
  D. Eppstein.
  Invited talk at DIMACS Worksh. on Geometric Optimization, New Brunswick, NJ, 2003.
  Plenary talk at ALGO 2004, Bergen, Norway, 2004.
  arxiv:cs.CG/0412046.
  Combinatorial and Computational Geometry, Goodman, Pach, and Welzl, eds., MSRI Publications 52, 2005, pp. 287-331.

  Defines quasiconvex programming, a form of generalized linear programming in which one seeks the point minimizing the pointwise maximum of a collection of quasiconvex functions. Surveys algorithms for solving quasiconvex programs either numerically or via generalizations of the dual simplex method from linear programming, and describe varied applications of this geometric optimization technique in meshing, scientific computation, information visualization, automated algorithm analysis, and robust statistics.

  (DIMACS talk slides -- ALGO talk slides)

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

Semi-automatically filtered from a common source file.