  We study fundamental graph parameters such as the Diameter and Radius in
directed graphs, when distances are measured using a somewhat unorthodox but
natural measure: the distance between $u$ and $v$ is the minimum of the
shortest path distances from $u$ to $v$ and from $v$ to $u$. The center node in
a graph under this measure can for instance represent the optimal location for
a hospital to ensure the fastest medical care for everyone, as one can either
go to the hospital, or a doctor can be sent to help.
  By computing All-Pairs Shortest Paths, all pairwise distances and thus the
parameters we study can be computed exactly in $\tilde{O}(mn)$ time for
directed graphs on $n$ vertices, $m$ edges and nonnegative edge weights.
Furthermore, this time bound is tight under the Strong Exponential Time
Hypothesis [Roditty-Vassilevska W. STOC 2013] so it is natural to study how
well these parameters can be approximated in $O(mn^{1-\epsilon})$ time for
constant $\epsilon>0$. Abboud, Vassilevska Williams, and Wang [SODA 2016] gave
a polynomial factor approximation for Diameter and Radius, as well as a
constant factor approximation for both problems in the special case where the
graph is a DAG. We greatly improve upon these bounds by providing the first
constant factor approximations for Diameter, Radius and the related
Eccentricities problem in general graphs. Additionally, we provide a hierarchy
of algorithms for Diameter that gives a time/accuracy trade-off.
