Despite significant recent progress on approximating graph spanners (subgraphs which approximately preserve distances), there are still several large gaps in our understanding. We give new results for two of them: approximating basic  k -spanner (particularly for small  k ), and the dependence on  f  when approximating  f -fault tolerant spanners.   We first design an O( n  1/3 )-approximation for 4-spanner (both basic and directed). This was the last value of  k  for which only an  O ([EQUATION])-approximation was known for basic  k -spanner, and thus implies that for any  k  the approximation ratio is at most  O ( n  1/3 ). For basic  k -spanner, we also show an integrality gap for the natural flow-based LP (the main tool in almost all nontrivial spanner approximations) which nearly matches the trivial approximation of  n  [EQUATION].   For  f -fault tolerant spanners, we show that in the small-stretch setting ( k  ∈ {3, 4}) it is possible to entirely remove the dependence on  f  from the approximation ratio, at the cost of moving to bicriteria guarantees. The previous best dependence on  f  was either almost-linear (in the undirected setting) or exponential (in the directed setting for stretch 4).
['Michael Dinitz', 'Z. Zhang']
Approximating low-stretch spanners