Improved Approximation of Min-Distances in Near-Linear Time
A randomized near-linear time algorithm is presented that achieves a $3-approximation to the min-diameter in near-linear time, dramatically improving over the previously best known $n$-approximation.