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) .
After revision:  STOC `17 , frequency, and the cost range.) In the high-frequency range, when f=\Omega(\log n), this was achieved by a deterministic O(\log n )-approximation algorithm for this problem that has an update time of O(f \log m) .