  This study considers the (soft) capacitated vertex cover problem in a dynamic
setting. This problem generalizes the dynamic model of the vertex cover
problem, which has been intensively studied in recent years. Given a
dynamically changing vertex-weighted graph $G=(V,E)$, which allows edge
insertions and edge deletions, the goal is to design a data structure that
maintains an approximate minimum vertex cover while satisfying the capacity
constraint of each vertex. That is, when picking a copy of a vertex $v$ in the
cover, the number of $v$'s incident edges covered by the copy is up to a given
capacity of $v$. We extend Bhattacharya et al.'s work [SODA'15 and ICALP'15] to
obtain a deterministic primal-dual algorithm for maintaining a constant-factor
approximate minimum capacitated vertex cover with $O(\log n / \epsilon)$
amortized update time, where $n$ is the number of vertices in the graph. The
algorithm can be extended to (1) a more general model in which each edge is
associated with a nonuniform and unsplittable demand, and (2) the more general
capacitated set cover problem.
