Again, no known constant factor approximation meets these desirable requirements on the update and query times. It is known how to achieve update and query time \(O(m^{1/k})\)  with approximation factor \(O(k)\)  in the partially dynamic (deletions only) case [1]} and approximation factor \((\log {n})^{O(k)}\)  in the fully dynamic case [2]}.
The only conditional lower bounds are for \((2-\varepsilon )\) -approximation algorithms and they follow directly from the lower bounds for the exact setting [3]}, [4]}, [5]}, where it is shown that distinguishing distance 2 from 4 is hard.The lower bounds hold even against much higher \(O(n^{1-\varepsilon })\)  update and query times, but inapproximability results with higher multiplicative factors are not known even if we demand \(m^{o(1)}\)  update and query times.
