Before revision:  STOC `17 designed a deterministic \Theta(\log m )-approximation algorithm for this problem that has an update time of O(f \log m) . On the other hand ] , the line of work by Bhattacharya et al.
After revision:  STOC `17 designed a deterministic \Theta(\log m )-approximation algorithm for this problem that has an update time of O(f \log n) amortized update time ] , the line of work by Bhattacharya et al.