TY - JOUR
AU - Li, Jiaoyang
AU - Felner, Ariel
AU - Koenig, Sven
AU - Kumar, T. K. Satish
PY - 2021/05/25
Y2 - 2024/02/26
TI - Using FastMap to Solve Graph Problems in a Euclidean Space
JF - Proceedings of the International Conference on Automated Planning and Scheduling
JA - ICAPS
VL - 29
IS - 1
SE - Main Track
DO - 10.1609/icaps.v29i1.3488
UR - https://ojs.aaai.org/index.php/ICAPS/article/view/3488
SP - 273-278
AB - <p>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.</p>
ER -