David Eppstein - Publications

Publications with Jean Cardinal

• Lazy algorithms for dynamic closest pair with arbitrary distance measures.
  J. Cardinal and D. Eppstein.
  Tech. Rep. 502, Univ. Libre de Bruxelles, Computer Science Dept., 2003.
  Worksh. Algorithm Engineering and Experiments (ALENEX), New Orleans, 2004, pp. 112–119.

  We modify my previous data structures for dynamic closest pairs, to use a lazy deletion mechanism, and show in experiments that the results are an improvement on the unmodified structures.

• Reconfiguration of satisfying assignments and subset sums: Easy to find, hard to connect.
  J. Cardinal, E. Demaine, D. Eppstein, R. Hearn, and A. Winslow.
  arXiv:1805.04055
  Proc. 24th International Computing and Combinatorics Conference (COCOON 2018), Qingdao, China.
  Springer, Lecture Notes in Comp. Sci. 10976 (2018), pp. 365–377.
  Theor. Comput. Sci. 806: 332–343, 2020.

  For several problems with polynomial-time solutions, we show that finding a sequence of steps that converts one solution into another (maintaining a valid solution at each step) is hard. These include planar monotone not-all-equal 3-sat, subset sum on integers of polynomial magnitude, and 0-1 integer programming with a constant number of linear inequality constraints.

  (Slides)