$\tilde{O}$ptimal Algorithm for 2-Approximate All Pair Shortest Paths -- almost

Manoj Gupta, Mrigankashekhar Shandilya

Given an undirected, unweighted graph $G$, we aim to compute a 2-approximation of all-pairs shortest paths (APSP). This problem admits a natural lower bound of $\hat{I}\text{c◯}(n^2)$ since the…