@article{Li_Felner_Koenig_Kumar_2021, title={Using FastMap to Solve Graph Problems in a Euclidean Space}, volume={29}, url={https://ojs.aaai.org/index.php/ICAPS/article/view/3488}, DOI={10.1609/icaps.v29i1.3488}, abstractNote={<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>}, number={1}, journal={Proceedings of the International Conference on Automated Planning and Scheduling}, author={Li, Jiaoyang and Felner, Ariel and Koenig, Sven and Kumar, T. K. Satish}, year={2021}, month={May}, pages={273-278} }