David Eppstein - Publications

• Optimal embedding into star metrics.
  D. Eppstein and K. Wortman.
  arXiv:0905.0283.
  Algorithms and Data Structures Symposium (WADS), Banff, Canada (best paper award).
  Springer, Lecture Notes in Comp. Sci. 5664, 2009, pp. 290–301.

  We provide an O(n³ log²n) algorithm for finding a non-distance-decreasing mapping from a given metric into a star metric with as small a dilation as possible. The main idea is to reduce the problem to one of parametric shortest paths in an auxiliary graph. Specifically, we transform the problem into the parametric negative cycle detection problem: given a graph in which the edge weights are linear functions of a parameter λ, find the minimum value of λ for which the graph contains no negative cycles. We find a new strongly polynomial time algorithm for this problem, and use it to solve the star metric embedding problem.

  (Slides)

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

Semi-automatically filtered from a common source file.