  In this paper, we study the set cover problem in the fully dynamic model. In
this model, the set of active elements, i.e., those that must be covered at any
given time, can change due to element arrivals and departures. The goal is to
maintain an algorithmic solution that is competitive with respect to the
current optimal solution. This model is popular in both the dynamic algorithms
and online algorithms communities. The difference is in the restriction placed
on the algorithm: in dynamic algorithms, the running time of the algorithm
making updates (called update time) is bounded, while in online algorithms, the
number of updates made to the solution (called recourse) is limited.
  In this paper we show the following results: In the update time setting, we
obtain O(log n)-competitiveness with O(f log n) amortized update time, and
O(f^3)-competitiveness with O(f^2) update time. The O(log n)-competitive
algorithm is the first one to achieve a competitive ratio independent of f in
this setting. In the recourse setting, we show a competitive ratio of O(min{log
n,f}) with constant amortized recourse. Note that this matches the best offline
bounds with just constant recourse, something that is impossible in the
classical online model.
  Our results are based on two algorithmic frameworks in the fully-dynamic
model that are inspired by the classic greedy and primal-dual algorithms for
offline set cover. We show that both frameworks can be used for obtaining both
recourse and update time bounds, thereby demonstrating algorithmic techniques
common to these strands of research.
