David Eppstein - Publications

J. Algorithms and Transactions on Algorithms

• Sequence comparison with mixed convex and concave costs.
  D. Eppstein.
  Tech. Rep. CUCS-382-88, Computer Science Dept., Columbia University, 1988.
  J. Algorithms 11 (1): 85–101, 1990.

  Gives an algorithm for finding the minimum number of mutations needed to transform one input string into another, in a general model in which substrings may be inserted or deleted at a cost depending nonlinearly on the substring length. The time bound depends on the number of times the second derivative of the cost function changes sign.

• Maintenance of a minimum spanning forest in a dynamic plane graph.
  D. Eppstein, G.F. Italiano, R. Tamassia, R.E. Tarjan, J. Westbrook, and M. Yung.
  1st ACM-SIAM Symp. Discrete Algorithms, San Francisco, 1990, pp. 1–11.
  J. Algorithms 13 (1): 33–54, 1992 (special issue for 1st Symp. Discrete Algorithms).
  Corrigendum, J. Algorithms 15: 173, 1993.

  The complement of a minimum spanning tree is a maximum spanning tree in the dual graph. By applying this fact we can use a modified form of Sleator and Tarjan's dynamic tree data structure to update the MST in logarithmic time per update.

• Offline algorithms for dynamic minimum spanning tree problems.
  D. Eppstein.
  2nd Worksh. Algorithms and Data Structures, Ottawa, Canada, 1991.
  Springer, Lecture Notes in Comp. Sci. 519, 1991, pp. 392–399.
  Tech. Rep. 92-04, ICS, UCI, 1992.
  J. Algorithms 17: 237–250, 1994.

  Given a sequence of edge insertions and deletions in a graph, finds the corresponding sequence of minimum spanning tree changes, in logarithmic time per update. Similarly solves the planar geometric version of the problem (using a novel "mixed MST" formulation in which part of the input is a graph and part is a point set) in time \(O(\log^2 n)\) for the Euclidean metric and \(O(\log n\log\log n)\) for the rectilinear metric.

• Minimum range balanced cuts via dynamic subset sums.
  D. Eppstein.
  Tech. Rep. 95-10, ICS, UCI, 1995.
  J. Algorithms 23: 375–385, 1997.

  Describes data structures for maintaining the solution of a dynamically changing subset sum problem, and uses them to find a cut in a graph minimizing the difference between the heaviest and lightest cut edge.

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

• Optimal point placement for mesh smoothing.
  N. Amenta, M. Bern, and D. Eppstein.
  8th ACM-SIAM Symp. Discrete Algorithms, New Orleans, 1997, pp. 528–537.
  Symp. Computational Geometry Approaches to Mesh Generation, SIAM 45th Anniversary Mtg., Stanford, 1997.
  arXiv:cs.CG/9809081.
  J. Algorithms 30: 302–322, 1999 (special issue for SODA 1997).

  We study finite element mesh smoothing problems in which we move vertex locations to optimize the shapes of nearby triangles. Many such problems can be solved in linear time using generalized linear programming; we also give efficient algorithms for some non-LP-type mesh smoothing problems. One lemma may be of independent interest: the locus of points in R^d from which a d-1 dimensional convex set subtends a given solid angle is convex.

  (SODA paper)

• Incremental and decremental maintenance of planar width.
  D. Eppstein.
  arXiv:cs.CG/9809038.
  10th ACM-SIAM Symp. Discrete Algorithms, Baltimore, 1999, pp. S899-S900.
  J. Algorithms 37 (2): 570–577, 2000.

  We show how to maintain the width of a planar point set, subject to insertions or deletions (but not both) in time O(n^c) per update for any c > 0. The idea is to apply our dynamic closest pair data structure to an appropriate measure of distance between pairs of convex hull features.

  (SODA talk slides)

• 3-coloring in time O(1.3289^n).
  R. Beigel and D. Eppstein.
  arXiv:cs.DS/0006046.
  J. Algorithms 54:2 (2005) 168-204.

  Journal paper combining 3-coloring algorithms from our FOCS '95 paper with improved bounds from our SODA '01 paper.

• Quasiconvex analysis of backtracking algorithms.
  D. Eppstein.
  arXiv:cs.DS/0304018.
  15th ACM-SIAM Symp. Discrete Algorithms, New Orleans, 2004, pp. 781–790.
  ACM Trans. Algorithms 2 (4): 492–509 (special issue for SODA 2004), 2006.

  We consider a class of multivariate recurrences frequently arising in the worst case analysis of Davis-Putnam-style exponential time backtracking algorithms for NP-hard problems. We describe a technique for proving asymptotic upper bounds on these recurrences, by using a suitable weight function to reduce the problem to that of solving univariate linear recurrences; show how to use quasiconvex programming to determine the weight function yielding the smallest upper bound; and prove that the resulting upper bounds are within a polynomial factor of the true asymptotics of the recurrence. We develop and implement a multiple-gradient descent algorithm for the resulting quasiconvex programs, using a real-number arithmetic package for guaranteed accuracy of the computed worst case time bounds.

  The journal version uses the longer title "Quasiconvex analysis of multivariate recurrence equations for backtracking algorithms".

  (SODA talk slides)