Using FastMap to Solve Graph Problems in a Euclidean Space

Authors

  • Jiaoyang Li University of Southern California
  • Ariel Felner Ben-Gurion University
  • Sven Koenig University of Southern California
  • T. K. Satish Kumar University of Southern California

Abstract

It is well known that many graph problems, like the Traveling Salesman Problem, are easier to solve in a Euclidean space. This motivates the idea of quickly preprocessing a given graph by embedding it in a Euclidean space to solve graph problems efficiently. In this paper, we study a nearlinear time algorithm, called FastMap, that embeds a given non-negative edge-weighted undirected graph in a Euclidean space and approximately preserves the pairwise shortest path distances between vertices. The Euclidean space can then be used either for heuristic guidance of A* (as suggested previously) or for geometric interpretations that facilitate the application of techniques from analytical geometry. We present a new variant of FastMap and compare it with the original variant theoretically and empirically. We demonstrate its usefulness for solving a path-finding and a multi-agent meeting problem.

Downloads

Published

2019-07-06

How to Cite

Li, J., Felner, A., Koenig, S., & Kumar, T. K. S. (2019). Using FastMap to Solve Graph Problems in a Euclidean Space. Proceedings of the International Conference on Automated Planning and Scheduling, 29(1), 273-278. Retrieved from https://ojs.aaai.org/index.php/ICAPS/article/view/3488